# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
225972 |
2020-04-22T06:54:26 Z |
balbit |
Dragon 2 (JOI17_dragon2) |
C++14 |
|
3744 ms |
7544 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
#define double long double
#define acos acosl
#define hypot hypotl
const int maxn = 1e5+5;
struct pt{
ll x, y;
pt operator - (pt oth) {
return {x-oth.x, y-oth.y};
}
ll operator * (pt oth) {
return x * (ll) oth.x + y * (ll) oth.y;
}
ll operator ^ (pt oth) {
return x * (ll) oth.y - y * (ll) oth.x;
}
};
struct Dg{
pt p;
double A, B;
bool above;
};
double getang(pt v, pt u) {
// from v to u, clockwise
return ((v*u) / (hypot(v.x, v.y) * hypot(u.x, u.y)));
}
const double PI = acos(-1);
vector<Dg> G[maxn];
signed main(){
int n,m; cin>>n>>m;
for(int i = 0; i<n; ++i) {
int a,b,c; cin>>a>>b>>c;
G[c].pb({{a,b},0,0});
}
pt S, T; cin>>S.x>>S.y>>T.x>>T.y;
for (int i = 1; i<=m; ++i) {
for (Dg & d : G[i]) {
d.A = getang(d.p-S, T-S);
d.B = getang(d.p-T, S-T);
bug(d.p.x, d.p.y);
bug(d.A, d.B);
d.above = ((T-S) ^ (d.p - S)) > 0;
bug(d.above);
}
}
int Q; cin>>Q;
while (Q--) {
int a,b; cin>>a>>b;
int ret = 0;
for (Dg &d1 : G[a]) {
for (Dg & d2 : G[b]) {
if (d1.above == d2.above) {
ret += ((((d1.p-S)^(d2.p-S))>0) != ((((d1.p-T)^(d2.p-T))) > 0)) && ((((T-S) ^ (d2.p-S)) > 0) == (((d2.p-S) ^ (d1.p-S)) > 0));
}else{
ret += ((((d1.p-S)^(d2.p-S))>0) != ((((d1.p-T)^(d2.p-T))) > 0));
}
}
}
cout<<ret<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3328 KB |
Output is correct |
2 |
Correct |
35 ms |
3072 KB |
Output is correct |
3 |
Correct |
59 ms |
3072 KB |
Output is correct |
4 |
Correct |
271 ms |
3960 KB |
Output is correct |
5 |
Correct |
293 ms |
4344 KB |
Output is correct |
6 |
Correct |
16 ms |
2944 KB |
Output is correct |
7 |
Correct |
16 ms |
2944 KB |
Output is correct |
8 |
Correct |
17 ms |
3072 KB |
Output is correct |
9 |
Correct |
16 ms |
3072 KB |
Output is correct |
10 |
Correct |
16 ms |
3072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1765 ms |
5512 KB |
Output is correct |
2 |
Correct |
3336 ms |
5524 KB |
Output is correct |
3 |
Correct |
108 ms |
6392 KB |
Output is correct |
4 |
Correct |
66 ms |
6392 KB |
Output is correct |
5 |
Correct |
71 ms |
5624 KB |
Output is correct |
6 |
Correct |
643 ms |
5388 KB |
Output is correct |
7 |
Correct |
645 ms |
5396 KB |
Output is correct |
8 |
Correct |
691 ms |
5476 KB |
Output is correct |
9 |
Correct |
660 ms |
5612 KB |
Output is correct |
10 |
Correct |
695 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3328 KB |
Output is correct |
2 |
Correct |
35 ms |
3072 KB |
Output is correct |
3 |
Correct |
59 ms |
3072 KB |
Output is correct |
4 |
Correct |
271 ms |
3960 KB |
Output is correct |
5 |
Correct |
293 ms |
4344 KB |
Output is correct |
6 |
Correct |
16 ms |
2944 KB |
Output is correct |
7 |
Correct |
16 ms |
2944 KB |
Output is correct |
8 |
Correct |
17 ms |
3072 KB |
Output is correct |
9 |
Correct |
16 ms |
3072 KB |
Output is correct |
10 |
Correct |
16 ms |
3072 KB |
Output is correct |
11 |
Correct |
1765 ms |
5512 KB |
Output is correct |
12 |
Correct |
3336 ms |
5524 KB |
Output is correct |
13 |
Correct |
108 ms |
6392 KB |
Output is correct |
14 |
Correct |
66 ms |
6392 KB |
Output is correct |
15 |
Correct |
71 ms |
5624 KB |
Output is correct |
16 |
Correct |
643 ms |
5388 KB |
Output is correct |
17 |
Correct |
645 ms |
5396 KB |
Output is correct |
18 |
Correct |
691 ms |
5476 KB |
Output is correct |
19 |
Correct |
660 ms |
5612 KB |
Output is correct |
20 |
Correct |
695 ms |
5240 KB |
Output is correct |
21 |
Correct |
1732 ms |
5476 KB |
Output is correct |
22 |
Correct |
3314 ms |
5720 KB |
Output is correct |
23 |
Correct |
2354 ms |
6904 KB |
Output is correct |
24 |
Correct |
915 ms |
7544 KB |
Output is correct |
25 |
Correct |
364 ms |
7160 KB |
Output is correct |
26 |
Correct |
359 ms |
7284 KB |
Output is correct |
27 |
Correct |
113 ms |
6008 KB |
Output is correct |
28 |
Correct |
109 ms |
6008 KB |
Output is correct |
29 |
Correct |
3744 ms |
7072 KB |
Output is correct |
30 |
Correct |
382 ms |
6704 KB |
Output is correct |
31 |
Correct |
359 ms |
6764 KB |
Output is correct |
32 |
Correct |
379 ms |
7416 KB |
Output is correct |
33 |
Correct |
1025 ms |
7420 KB |
Output is correct |
34 |
Correct |
346 ms |
7544 KB |
Output is correct |
35 |
Correct |
336 ms |
7032 KB |
Output is correct |
36 |
Correct |
345 ms |
6904 KB |
Output is correct |
37 |
Correct |
372 ms |
7160 KB |
Output is correct |
38 |
Correct |
1610 ms |
7288 KB |
Output is correct |
39 |
Correct |
1523 ms |
7092 KB |
Output is correct |
40 |
Correct |
1161 ms |
7424 KB |
Output is correct |
41 |
Correct |
2717 ms |
7012 KB |
Output is correct |
42 |
Correct |
1855 ms |
6764 KB |
Output is correct |
43 |
Correct |
2021 ms |
6748 KB |
Output is correct |
44 |
Correct |
1844 ms |
6212 KB |
Output is correct |
45 |
Correct |
878 ms |
5868 KB |
Output is correct |
46 |
Correct |
561 ms |
5728 KB |
Output is correct |
47 |
Correct |
1040 ms |
5752 KB |
Output is correct |
48 |
Correct |
887 ms |
5860 KB |
Output is correct |
49 |
Correct |
671 ms |
5860 KB |
Output is correct |