| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 156297 |
2019-10-05T00:42:51 Z |
tduong0806 |
Tri (CEOI09_tri) |
C++14 |
|
2000 ms |
5808 KB |
#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
tri.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
504 KB |
Output is correct |
| 2 |
Correct |
11 ms |
376 KB |
Output is correct |
| 3 |
Execution timed out |
2031 ms |
1980 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2047 ms |
2412 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2051 ms |
4088 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2079 ms |
4048 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2062 ms |
4716 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2065 ms |
5208 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2060 ms |
5672 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2044 ms |
5808 KB |
Time limit exceeded |
