oj.uz

Submission #369311

# Submission time Handle Problem Language Result Execution time Memory
369311 2021-02-21T09:22:31 Z denkendoemeer Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 6252 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;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3052 KB Output is correct
2 Correct 31 ms 3052 KB Output is correct
3 Correct 55 ms 3052 KB Output is correct
4 Correct 300 ms 3180 KB Output is correct
5 Correct 297 ms 3052 KB Output is correct
6 Correct 11 ms 2924 KB Output is correct
7 Correct 11 ms 2924 KB Output is correct
8 Correct 13 ms 2924 KB Output is correct
9 Correct 12 ms 2924 KB Output is correct
10 Correct 12 ms 3052 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 4608 KB Output is correct
2 Correct 3369 ms 4836 KB Output is correct
3 Correct 101 ms 5740 KB Output is correct
4 Correct 57 ms 5868 KB Output is correct
5 Correct 61 ms 4972 KB Output is correct
6 Correct 629 ms 4612 KB Output is correct
7 Correct 630 ms 4612 KB Output is correct
8 Correct 719 ms 4696 KB Output is correct
9 Correct 677 ms 5088 KB Output is correct
10 Correct 706 ms 4828 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3052 KB Output is correct
2 Correct 31 ms 3052 KB Output is correct
3 Correct 55 ms 3052 KB Output is correct
4 Correct 300 ms 3180 KB Output is correct
5 Correct 297 ms 3052 KB Output is correct
6 Correct 11 ms 2924 KB Output is correct
7 Correct 11 ms 2924 KB Output is correct
8 Correct 13 ms 2924 KB Output is correct
9 Correct 12 ms 2924 KB Output is correct
10 Correct 12 ms 3052 KB Output is correct
11 Correct 1784 ms 4608 KB Output is correct
12 Correct 3369 ms 4836 KB Output is correct
13 Correct 101 ms 5740 KB Output is correct
14 Correct 57 ms 5868 KB Output is correct
15 Correct 61 ms 4972 KB Output is correct
16 Correct 629 ms 4612 KB Output is correct
17 Correct 630 ms 4612 KB Output is correct
18 Correct 719 ms 4696 KB Output is correct
19 Correct 677 ms 5088 KB Output is correct
20 Correct 706 ms 4828 KB Output is correct
21 Correct 1783 ms 4824 KB Output is correct
22 Correct 3361 ms 4928 KB Output is correct
23 Correct 2414 ms 6252 KB Output is correct
24 Correct 959 ms 6252 KB Output is correct
25 Correct 365 ms 5484 KB Output is correct
26 Correct 358 ms 5228 KB Output is correct
27 Correct 98 ms 5100 KB Output is correct
28 Correct 98 ms 5088 KB Output is correct
29 Execution timed out 4042 ms 5424 KB Time limit exceeded
30 Halted 0 ms 0 KB -