Submission #369181

#	Time	Username	Problem	Language	Result	Execution time	Memory
369181		denkendoemeer	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4040 ms	5252 KiB

dragon2

#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){
                    if ((((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))
                        ans++;
                }
                else{
                    if ((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0))
                        ans++;
                }
            }
        }
        cout<<ans<<'\n';
    }
return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40