1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
x=0; char c=getchar(); int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
struct Point {
ll x,y;
Point (ll x=0,ll y=0): x(x),y(y) {}
friend Point operator +(Point A,Point B) { return Point(A.x+B.x,A.y+B.y); }
friend Point operator -(Point A,Point B) { return Point(A.x-B.x,A.y-B.y); }
friend Point operator *(Point A,ll B) { return Point(A.x*B,A.y*B); }
friend Point operator /(Point A,ll B) { return Point(A.x/B,A.y/B); }
friend bool operator < (Point A,Point B) { return A.x<B.x; }
};
ll Cross(Point A,Point B) { return A.x*B.y-A.y*B.x; }
set<Point> s1,s2;
bool be_under(Point A) {
set<Point>::iterator it1=s1.lower_bound(A),it2;
if(it1==s1.end()) return 0;
if((*it1).x==A.x) return (*it1).y>=A.y;
if(it1==s1.begin()) return 0;
it2=it1,it2--;
return Cross(A-(*it2),(*it1)-(*it2))>=0;
}
bool be_upper(Point A) {
set<Point>::iterator it1=s2.lower_bound(A),it2;
if(it1==s2.end()) return 0;
if((*it1).x==A.x) return (*it1).y<=A.y;
if(it1==s2.begin()) return 0;
it2=it1,it2--;
return Cross((*it1)-(*it2),A-(*it2))>=0;
}
void insert_down(Point A) {
if(s2.empty()) { s2.insert(A); return; }
set<Point>::iterator pre=s2.upper_bound(A),ppre;
if(pre!=s2.begin()) {
pre--;
while(pre!=s2.begin()) {
ppre=pre,--ppre;
if(Cross((*pre)-(*ppre),A-(*ppre))<=0) s2.erase(*pre),pre=ppre;
else break;
}
if(pre==s2.begin())
if((*pre).x==A.x) s2.erase(*pre);
}
set<Point>::iterator suf=s2.lower_bound(A),ssuf;
if(suf!=s2.end()) {
ssuf=suf,++ssuf;
while(ssuf!=s2.end()) {
if(Cross((*suf)-A,(*ssuf)-A)<=0) s2.erase(*suf),suf=ssuf;
else break;
++ssuf;
}
if(ssuf==s2.end())
if((*suf).x==A.x) s2.erase(*suf);
}
s2.insert(A);
}
void insert_up(Point A) {
if(s1.empty()) { s1.insert(A); return; }
set<Point>::iterator pre=s1.upper_bound(A),ppre;
if(pre!=s1.begin()) {
pre--;
while(pre!=s1.begin()) {
ppre=pre,--ppre;
if(Cross((*pre)-(*ppre),A-(*ppre))>=0) s1.erase(*pre),pre=ppre;
else break;
}
if(pre==s1.begin())
if((*pre).x==A.x) s1.erase(*pre);
}
set<Point>::iterator suf=s1.lower_bound(A),ssuf;
if(suf!=s1.end()) {
ssuf=suf,++ssuf;
while(ssuf!=s1.end()) {
if(Cross((*suf)-A,(*ssuf)-A)>=0) s1.erase(*suf);
else break;
suf=ssuf,++ssuf;
}
if(ssuf==s1.end())
if((*suf).x==A.x) s1.erase(*suf);
}
s1.insert(A);
}
void Debug() {
cout<<"upper:";
for(set<Point>::iterator it=s1.begin();it!=s1.end();++it) printf("%lld %lld ",it->x,it->y);
puts("");
cout<<"lower:";
for(set<Point>::iterator it=s2.begin();it!=s2.end();++it) printf("%lld %lld ",it->x,it->y);
puts("");
}
int main() {
int q,ty; Point p;
rd(q);
for(int i=1;i<=2;++i,q--) {
rd(ty),rd(p.x),rd(p.y);
insert_down(p),insert_up(p);
}
while(q--) {
rd(ty),rd(p.x),rd(p.y);
if(ty==1) {
if(!be_under(p)) insert_up(p);
if(!be_upper(p)) insert_down(p);
}
else {
if(be_under(p)&&be_upper(p)) puts("YES");
else puts("NO");
}
}
return 0;
}
|