Submission #369351

#	Time	Username	Problem	Language	Result	Execution time	Memory
369351		denkendoemeer	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1612 ms	11208 KiB

dragon2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct pct
{
    int x,y,c;
    int u1,u2;
}v[30005],s,e;
ll cross(pct a,pct b,pct c)
{
    return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(c.x-a.x)*(b.y-a.y);
}
int stx[30005],sty[30005],edx[30005],edy[30005],n,m;
bool cmp(pct a,pct b)
{
    bool ok1,ok2;
    ok1=cross(s,e,a)>0;
    ok2=cross(s,e,b)>0;
    if (ok1!=ok2)
        return ok1>ok2;
    return cross(s,a,b)>0;
}
bool cmp2(pct a,pct b)
{
    bool ok1,ok2;
    ok1=cross(s,e,a)>0;
    ok2=cross(s,e,b)>0;
    if (ok1!=ok2)
        return ok1>ok2;
    return cross(e,a,b)>0;
}
void calc1()
{
    sort(v,v+n,cmp);
    int mini=0,i;
    for(i=0;i<n;i++){
        v[i].u1=i;
        if (cross(s,e,v[i])>0)
            mini=i+1;
    }
    int u=0;
    for(i=mini;i<n;i++){
        while(u<mini && cross(s,v[i],v[u])>0)
            u++;
        stx[i]=i;
        edx[i]=u;
    }
    u=mini;
    for(i=0;i<mini;i++){
        while(u<n && cross(s,v[i],v[u])>0)
            u++;
        stx[i]=u;
        edx[i]=i;
    }
}
void calc2()
{
    sort(v,v+n,cmp2);
    int mini=0,i;
    for(i=0;i<n;i++){
        v[i].u2=i;
        if (cross(s,e,v[i])>0)
            mini=i+1;
    }
    int u=0;
    for(i=mini;i<n;i++){
        while(u<mini && cross(e,v[i],v[u])>0)
            u++;
        sty[i]=u;
        edy[i]=i;
    }
    u=mini;
    for(i=0;i<mini;i++){
        while(u<n && cross(e,v[i],v[u])>0)
            u++;
        sty[i]=i;
        edy[i]=u;
    }
}
vector<pair<int,int>>g[30005];
map<pair<int,int>,int>mp;
int calc(int x,int y)
{
    if (mp.find(make_pair(x,y))!=mp.end())
        return mp[make_pair(x,y)];
    int ans=0;
    for(auto it:g[x])
        for(auto it2:g[y]){
            bool ok1=0,ok2=0;
            if (!(edx[it.first]<=it2.first && it2.first<stx[it.first]))
                ok1=1;
            if (sty[it.second]<=it2.second && it2.second<edy[it.second])
                ok2=1;
            if (ok1 && ok2)
                ans++;
        }
    mp[make_pair(x,y)]=ans;
    return ans;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int q,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
    calc1();
    calc2();
    for(i=0;i<n;i++)
        g[v[i].c].push_back(make_pair(v[i].u1,v[i].u2));
    scanf("%d",&q);
    int x,y;
    for(i=1;i<=q;i++){
        scanf("%d%d",&x,&y);
        printf("%d\n",calc(x,y));
    }
return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |     scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
dragon2.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

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