Submission #156297

#	Time	Username	Problem	Language	Result	Execution time	Memory
156297		tduong0806	Tri (CEOI09_tri)	C++14	20 / 100	2079 ms	5808 KiB

tri

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
const int N=1e5+10;
int n,m;
pii a[N];
bool cmp(pii u,pii v)
{
    return 1ll*u.fi*v.se>1ll*v.fi*u.se;
}
ll S(pii a,pii b,pii c)
{
    ll ret=0;
    ret=ret+1ll*(a.fi-b.fi)*(a.se+b.se);
    ret=ret+1ll*(b.fi-c.fi)*(b.se+c.se);
    ret=ret+1ll*(c.fi-a.fi)*(c.se+a.se);
    return abs(ret);
}
bool kt(pii a,pii b,pii c,pii d)
{
    return (S(a,b,d)+S(b,c,d)+S(a,c,d))==S(a,b,c);
}
main()
{
    //freopen("TRI.inp","r",stdin);
    //freopen("TRI.out","w",stdout);
    n=in,m=in;
    forinc(i,1,n) a[i]={in,in};
    sort(a+1,a+n+1,cmp);
    //forinc(i,1,n) cout<<a[i].fi<<" "<<a[i].se<<endl;
    while(m--)
    {
        pii x={in,in},y={in,in},z={0,0};
        if(cmp(y,x)) swap(x,y);
        int l=lower_bound(a+1,a+n+1,x,cmp)-a,r=upper_bound(a+1,a+n+1,y,cmp)-a-1;
        bool ok=0;
        forinc(i,l,r) if(kt(x,y,z,a[i])) {ok=1;break;}
        cout<<(ok?'Y':'N')<<"\n";
    }
}

Compilation message (stderr)

tri.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 20 / 100