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
|
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N, C;
cin >> N >>> C;
double r = C / (2 * pi);
vector<int> temp, P;
int t;
for (int i = 0;i < N; i++)
{
cin >> t;
temp.push_back(t); // REMEMBER ITS starting from 0 now not 1
P.push_back(to_coordinates(t));
}
int output = 0;
for subset in combinations(P.keys(), 3):
if is_good(subset):
output += 1;
cout << output << endl;
return 0;
}
//from math import pi, cos, sin
//from itertools import permutations, combinations
bool in_triangle(double ax,double ay,double bx,double by,double cx,double cy)
{
double px= r, py = r;
try:
w1 = (ax * (cy - ay) + (py - ay) * (cx - ax) - px * (cy - ay)) / ((by - ay) * (cx - ax) - (bx - ax) * (cy - ay));
w2 = (py - ay - w1 * (by - ay)) / (cy - ay);
except:
return false;
if (w1 >= 0 && w2 >= 0 && w1 + w2 <= 1):
return true;
return false;
}
vector<double> to_coordinates(int p)
{
double angle = p / static_cast<double>(C) * 2 * pi;
return {r * cos(angle) + r, r * sin(angle) + r};
}
bool is_opposite(int a,int b)
{
if (abs(temp[a] - temp[b]) == C / 2):
return true;
return false;
}
bool is_good(vector<int> subset)
{
t = {i: [] for i in subset}
for a, b, c in permutations(subset, 3):
t[a].append((a, b, c))
for i in subset:
a1, b1, c1 = t[i][0]
ax1, ay1 = P[a1]
bx1, by1 = P[b1]
cx1, cy1 = P[c1]
a2, b2, c2 = t[i][1]
ax2, ay2 = P[a2]
bx2, by2 = P[b2]
cx2, cy2 = P[c2]
if not (in_triangle(ax1, ay1, bx1, by1, cx1, cy1) or in_triangle(ax2, ay2, bx2, by2, cx2, cy2)):
return false;
for a, b in combinations(subset, 2):
if is_opposite(a, b):
return false;
return true;
}
|
