#include <iostream>
#include <vector>
#include <algorithm>
#define DIM 100010
#define x first
#define y second
using namespace std;
pair<int,int> points[DIM];
vector < pair<int,int> > aint[4*DIM],d;
int n,q,i,ok;
pair<int,int> a,b;
inline long long get_det (pair<int,int> a, pair<int,int> b, pair<int,int> c){
return 1LL*(b.x-a.x)*(c.y-a.y) - 1LL*(b.y-a.y)*(c.x-a.x);
}
inline int cmp (pair<int,int> a, pair<int,int> b){
return get_det (make_pair(0,0),a,b) < 0;
}
inline int binarySearch_aint (vector< pair<int,int> > v, pair<int,int> a, pair<int,int> b){
/// daca gasesc vreun punct situat sub dreapta a,b
int st = 0, dr = v.size()-2;
while (st <= dr){
int mid = (st+dr)>>1;
if (get_det(a,b,v[mid]) >= get_det(a,b,v[mid+1]))
st = mid+1;
else dr = mid-1;
}
if (get_det(a,b,v[st]) < 0)
return 1;
return 0;
}
inline int binarySearch (pair<int,int> v[], pair<int,int> point){
int st = 1, dr = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (get_det(make_pair(0,0),point,v[mid]) <= 0)
dr = mid-1;
else st = mid+1;
}
return st;
}
inline void build (int nod, int st, int dr){
if (st == dr){
aint[nod].push_back(points[st]);
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
/// acum trebuie sa fac infasuratoarea convexa pt intervalul st dr
aint[nod].push_back(points[st]);
aint[nod].push_back(points[st+1]);
for (int i=st+2;i<=dr;i++){
while (aint[nod].size() >= 2 && get_det(aint[nod][aint[nod].size()-2],aint[nod][aint[nod].size()-1],points[i]) <= 0)
aint[nod].pop_back();
aint[nod].push_back(points[i]);
}}
inline void query (int nod, int st, int dr, int x, int y){
if (ok)
return;
if (x <= st && dr <= y){
/// vreau sa vad daca am macar un punct sub latura triunghiului care nu are niciun punct in origine
int l = 0, r = aint[nod].size()-2;
while (l <= r){
int m = (l+r)>>1;
if (get_det(a,b,aint[nod][m]) >= get_det(a,b,aint[nod][m+1]))
l = m+1;
else r = m-1;
}
if (get_det(a,b,aint[nod][l]) < 0)
ok = 1;
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
//InParser fin ("tri3.in");
//ofstream fout ("tri3.out");
cin>>n>>q;
for (i=1;i<=n;++i)
cin>>points[i].x>>points[i].y;
/// sortez punctele dupa unghi
sort (points+1,points+n+1,cmp);
build (1,1,n);
for (;q--;){
cin>>a.x>>a.y>>b.x>>b.y;
if (get_det(make_pair(0,0),a,b) > 0)
swap (a,b);
/// trebuie sa gasesc intervalul de puncte care e cuprins intre cele doua laturi care pleaca din origine
int poz1 = binarySearch(points,a);
int poz2 = binarySearch(points,b);
--poz2; /// cautarea imi da punctul imediat dupa
if (poz1 <= poz2){
ok = 0;
query (1,1,n,poz1,poz2);
(ok) ? (cout<<"Y\n") : (cout<<"N\n");
} else cout<<"N\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
17 ms |
9848 KB |
Output is correct |
| 3 |
Correct |
201 ms |
13444 KB |
Output is correct |
| 4 |
Correct |
365 ms |
19316 KB |
Output is correct |
| 5 |
Correct |
729 ms |
28160 KB |
Output is correct |
| 6 |
Correct |
741 ms |
20640 KB |
Output is correct |
| 7 |
Correct |
973 ms |
23760 KB |
Output is correct |
| 8 |
Correct |
780 ms |
23904 KB |
Output is correct |
| 9 |
Correct |
896 ms |
25456 KB |
Output is correct |
| 10 |
Correct |
962 ms |
26756 KB |
Output is correct |
