oj.uz

Submission #369307

# Submission time Handle Problem Language Result Execution time Memory
369307 2021-02-21T09:13:36 Z denkendoemeer Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 6560 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct pct
{
    ll x,y;
    pct operator - (pct aux)
    {
        return {x-aux.x,y-aux.y};
    }
    ll operator * (pct aux)
    {
        return 1LL*x*aux.x+1LL*y*aux.y;
    }
    ll operator ^ (pct aux)
    {
        return 1LL*x*aux.y-1LL*y*aux.x;
    }
};
struct aux
{
    pct p;
    double a,b;
    bool ok;
};
double unghi(pct x,pct y)
{
    return ((x*y)/(hypotl(x.x,x.y)*hypotl(y.x,y.y)));
}
const double pi=acos(-1);
vector<aux>g[100005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    int i;
    for(i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[c].push_back({{a,b},0,0});
    }
    pct s,t;
    cin>>s.x>>s.y>>t.x>>t.y;
    for(i=1;i<=m;i++){
        for(aux &it:g[i]){
            it.a=unghi(it.p-s,t-s);
            it.b=unghi(it.p-t,s-t);
            if (((t-s)^(it.p-s))>0)
                it.ok=1;
            else
                it.ok=0;
        }
    }
    int q;
    cin>>q;
    for(i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        int ans=0;
        for(aux &it1:g[a]){
            for(aux &it2:g[b]){
                if (it1.ok==it2.ok){
                    ans=ans+(((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0)) && ((((t-s)^(it2.p-s))>0)==(((it2.p-s)^(it1.p-s))>0)));
                }
                else{
                    ans=ans+((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0));

                }
            }
        }
        cout<<ans<<endl;
    }
return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2960 KB Output is correct
2 Correct 28 ms 2924 KB Output is correct
3 Correct 50 ms 3052 KB Output is correct
4 Correct 251 ms 3948 KB Output is correct
5 Correct 242 ms 4076 KB Output is correct
6 Correct 7 ms 2924 KB Output is correct
7 Correct 8 ms 2924 KB Output is correct
8 Correct 11 ms 2924 KB Output is correct
9 Correct 10 ms 3068 KB Output is correct
10 Correct 10 ms 2924 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1764 ms 4284 KB Output is correct
2 Correct 3389 ms 5180 KB Output is correct
3 Correct 79 ms 5484 KB Output is correct
4 Correct 26 ms 5356 KB Output is correct
5 Correct 26 ms 4972 KB Output is correct
6 Correct 607 ms 4756 KB Output is correct
7 Correct 594 ms 4680 KB Output is correct
8 Correct 675 ms 4676 KB Output is correct
9 Correct 647 ms 4708 KB Output is correct
10 Correct 683 ms 4576 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2960 KB Output is correct
2 Correct 28 ms 2924 KB Output is correct
3 Correct 50 ms 3052 KB Output is correct
4 Correct 251 ms 3948 KB Output is correct
5 Correct 242 ms 4076 KB Output is correct
6 Correct 7 ms 2924 KB Output is correct
7 Correct 8 ms 2924 KB Output is correct
8 Correct 11 ms 2924 KB Output is correct
9 Correct 10 ms 3068 KB Output is correct
10 Correct 10 ms 2924 KB Output is correct
11 Correct 1764 ms 4284 KB Output is correct
12 Correct 3389 ms 5180 KB Output is correct
13 Correct 79 ms 5484 KB Output is correct
14 Correct 26 ms 5356 KB Output is correct
15 Correct 26 ms 4972 KB Output is correct
16 Correct 607 ms 4756 KB Output is correct
17 Correct 594 ms 4680 KB Output is correct
18 Correct 675 ms 4676 KB Output is correct
19 Correct 647 ms 4708 KB Output is correct
20 Correct 683 ms 4576 KB Output is correct
21 Correct 1747 ms 4808 KB Output is correct
22 Correct 3349 ms 5068 KB Output is correct
23 Correct 2387 ms 5764 KB Output is correct
24 Correct 884 ms 6560 KB Output is correct
25 Correct 283 ms 6252 KB Output is correct
26 Correct 302 ms 6252 KB Output is correct
27 Correct 59 ms 5356 KB Output is correct
28 Correct 56 ms 5100 KB Output is correct
29 Execution timed out 4067 ms 6380 KB Time limit exceeded
30 Halted 0 ms 0 KB -