Submission #64791

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <cassert>
#include <stack>
#include <climits>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <memory>
#include <functional>
#include <cfloat>
#include <numeric>
#include <random>
#include <sstream>
#include <bitset>
using namespace std;
const double PI = std::acos(-1);
static double radius;
struct Angle {
double sin, cos;
static Angle from_cos(const double cos) {
return Angle{ std::sqrt(1 - cos * cos), cos };
}
static Angle from_sin(const double sin) {
return Angle{ sin, std::sqrt(1 - sin * sin) };
}
double radian() const {
return (sin >= 0) ? std::acos(cos) : 2 * PI - std::acos(cos);
}
Angle operator+(const Angle other) const {
return Angle{ sin * other.cos + cos * other.sin, cos * other.cos - sin * other.sin };
}
Angle operator-() const {
return Angle{ -sin, cos };
}
};
struct Vector {
double dx, dy;
double cross(const Vector other) const {
return dx * other.dy - dy * other.dx;
}
double dot(const Vector other) const {
return dx * other.dx + dy * other.dy;
}
double length() const {
return std::sqrt(dx * dx + dy * dy);
}
Angle angle_to(const Vector other) const {
const auto len = length() * other.length();
return Angle{ cross(other) / len, dot(other) / len };
}
Vector rotate(const Angle angle) const {
return Vector{ dx * angle.cos - dy * angle.sin, dy * angle.cos + dx * angle.sin };
}
Vector change_length(const double new_length) const {
const auto ratio = new_length / length();
return Vector{ dx * ratio, dy * ratio };
}
};
struct Point {
double x, y;
Vector diff_to(const Point to) const {
return Vector{ to.x - x, to.y - y };
}
Point move(const Vector other) const {
return Point{ x + other.dx, y + other.dy };
}
double distance(const Point other) const {
return diff_to(other).length();
}
};
double area() {
return radius * radius * PI;
}
double intersect(const Point a, const Point b) {
const auto dist = a.distance(b);
if (dist >= radius * 2) return 0;
const auto angle_half = Angle::from_cos(dist / 2 / radius);
const auto base = a.diff_to(b).change_length(radius);
const auto angle = angle_half + angle_half;
const auto triangle = angle.sin * radius * radius;
const auto piece = angle.radian() / PI * area();
return piece - triangle;
}
std::vector<Point> cross_point(const Point a, const Point b) {
const auto dist = a.distance(b);
if (dist >= radius * 2) return {};
const auto angle = Angle::from_cos(dist / 2 / radius);
const auto base = a.diff_to(b).change_length(radius);
return { a.move(base.rotate(angle)), a.move(base.rotate(-angle)) };
}
double union_type1(const Point a, const Point b, const Point c) {
return area() * 3 - intersect(b, c) - intersect(c, a);
}
double triangle_area(const std::vector<Point> points) {
assert(points.size() == 3);
double sum{ 0 };
std::vector<double> edges;
for (auto i = 0; i < 3; ++i) {
const auto dist = points[i].distance(points[(i + 1) % 3]);
edges.push_back(dist);
const auto angle_half = Angle::from_sin(dist / 2 / radius);
const auto angle = angle_half + angle_half;
sum += area() * angle.radian() / 2 / PI - angle.sin * radius * radius / 2;
}
const auto s = std::accumulate(edges.begin(), edges.end(), 0.0) / 2;
return sum + std::sqrt(s * (s - edges[0]) * (s - edges[1]) * (s - edges[2]));
}
double union_type0(const Point a, const Point b, const Point c) {
std::vector<Point> inner_point;
for (const auto p : cross_point(a, b)) {
if (p.distance(c) < radius) {
inner_point.push_back(p);
}
}
for (const auto p : cross_point(b, c)) {
if (p.distance(a) < radius) {
inner_point.push_back(p);
}
}
for (const auto p : cross_point(c, a)) {
if (p.distance(b) < radius) {
inner_point.push_back(p);
}
}
if (inner_point.size() == 3) return area() * 3 - intersect(a, b) - intersect(b, c) - intersect(c, a) + triangle_area(inner_point);
else return area() * 3 - intersect(a, b) - intersect(b, c) - intersect(c, a);
}
double solve(const std::vector<Point> points) {
for (auto i = 0; i < 3; ++i) {
int count{ 0 };
for (const auto p : cross_point(points[(i + 1) % 3], points[(i + 2) % 3])) {
if (points[i].distance(p) < radius) {
++count;
}
}
if (count == 2) {
return union_type1(points[(i + 1) % 3], points[(i + 2) % 3], points[i]);
}
}
return union_type0(points[0], points[1], points[2]);
}
int main() {
std::cin >> radius;
std::vector<Point> points(3);
for (auto& p : points) std::cin >> p.x >> p.y;
std::cout << std::setprecision(15) << std::fixed << solve(points) << '\n';
}

ステータス

項目 データ
問題 1459 - 柿の実
ユーザー名 syoribu
投稿日時 2020-11-20 12:29:33
言語 C++17
状態 Accepted
得点 11
ソースコード長 4877 Byte
最大実行時間 26 ms
最大メモリ使用量 740 KB

セット

セット 得点 Cases
1 ALL 11 / 11 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 23 ms 604 KB
1
in2 AC 17 ms 432 KB
1
in3 AC 21 ms 580 KB
1
in4 AC 21 ms 548 KB
1
in5 AC 17 ms 640 KB
1
in6 AC 24 ms 608 KB
1
in7 AC 23 ms 576 KB
1
in8 AC 24 ms 552 KB
1
in9 AC 18 ms 524 KB
1
in10 AC 24 ms 704 KB
1
in11 AC 21 ms 548 KB
1
in12 AC 23 ms 520 KB
1
in13 AC 25 ms 620 KB
1
in14 AC 15 ms 592 KB
1
in15 AC 20 ms 436 KB
1
in16 AC 16 ms 408 KB
1
in17 AC 24 ms 640 KB
1
in18 AC 21 ms 740 KB
1
in19 AC 25 ms 588 KB
1
in20 AC 23 ms 532 KB
1
in21 AC 16 ms 624 KB
1
in22 AC 26 ms 468 KB
1
in23 AC 21 ms 568 KB
1
in24 AC 21 ms 536 KB
1
in25 AC 18 ms 636 KB
1
in26 AC 17 ms 604 KB
1