#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef __int128 ld;
const int N = 100100;
ll T;
int n, x[N], y[N];
bool cw(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3){
return (x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3) < 0;
}
bool get(int id, ld x3, ld y3){
int nt = (id + 1);
if (nt == n) nt = 0;
return !cw(x[id], y[id], x[nt], y[nt], x3, y3);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif // _LOCAL
cin >> T >> n;
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
int qq; cin >> qq;
int p1 = 0, p2 = n / 2;
ll kol = 0;
for (; qq; qq--){
ll CX, CY; cin >> CX >> CY;
CX ^= (T * kol * kol * kol);
CY ^= (T * kol * kol * kol);
ld cx = CX, cy = CY;
bool fi = get(p1, cx, cy);
bool se = get(p2, cx, cy);
if (fi && se){
cout << "DA\n";
kol++;
} else if (!fi && !se){
cout << "NE\n";
} else {
if (!fi) swap(p1, p2);
int l1 = 1, r1 = n / 2;
while (l1 < r1){
int md = (l1 + r1 + 1) >> 1;
if (get((p1 - md + 1 + n) % n, cx, cy))
l1 = md;
else r1 = md - 1;
}
int l2 = 1, r2 = n / 2;
while (l2 < r2){
int md = (l2 + r2 + 1) >> 1;
if (get((p1 + md - 1) % n, cx, cy))
l2 = md;
else r2 = md - 1;
}
if ((l1 + l2 - 1) > n / 2) {
cout << "DA\n";
kol++;
} else cout << "NE\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
400 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
384 KB |
Output is correct |
7 |
Correct |
7 ms |
384 KB |
Output is correct |
8 |
Correct |
7 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
384 KB |
Output is correct |
11 |
Correct |
7 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
400 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
384 KB |
Output is correct |
7 |
Correct |
7 ms |
384 KB |
Output is correct |
8 |
Correct |
7 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
384 KB |
Output is correct |
11 |
Correct |
7 ms |
384 KB |
Output is correct |
12 |
Correct |
76 ms |
632 KB |
Output is correct |
13 |
Correct |
96 ms |
632 KB |
Output is correct |
14 |
Correct |
112 ms |
760 KB |
Output is correct |
15 |
Correct |
122 ms |
888 KB |
Output is correct |
16 |
Correct |
154 ms |
1272 KB |
Output is correct |
17 |
Correct |
149 ms |
1400 KB |
Output is correct |
18 |
Correct |
99 ms |
632 KB |
Output is correct |
19 |
Correct |
118 ms |
828 KB |
Output is correct |
20 |
Correct |
145 ms |
1108 KB |
Output is correct |
21 |
Correct |
152 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
1480 KB |
Output is correct |
2 |
Correct |
157 ms |
1400 KB |
Output is correct |
3 |
Correct |
123 ms |
888 KB |
Output is correct |
4 |
Correct |
162 ms |
1400 KB |
Output is correct |
5 |
Correct |
163 ms |
1376 KB |
Output is correct |
6 |
Correct |
152 ms |
1400 KB |
Output is correct |
7 |
Correct |
151 ms |
1272 KB |
Output is correct |
8 |
Correct |
157 ms |
1528 KB |
Output is correct |
9 |
Correct |
150 ms |
1248 KB |
Output is correct |