【动态凸包模板】wa on task7 求助
查看原帖
【动态凸包模板】wa on task7 求助
124918
LinkyChristian楼主2021/12/31 13:23

RT,第7个点挂了,交了一整页了,求大佬帮助

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct node{
	int x,y;
}pot[N],p0;
set<node> st;
int n;
int check(node a1,node b1,node a0,node b0) {
	return (a1.x-a0.x)*(b1.y-b0.y)-(b1.x-b0.x)*(a1.y-a0.y);
}
int dis(node a1,node a0) {
	return (a1.x-a0.x)*(a1.x-a0.x)+(a1.y-a0.y)*(a1.y-a0.y);
}
bool operator<(node a1,node a2) {
	double tmp=check(a1,a2,p0,p0);
	return tmp==0?a1.x<a2.x:tmp>0;
}             
node sk[N];              
int cnt,opt[N];
set<node>::iterator suc,pre,del;
set<node>::iterator PRE(set<node>::iterator x) {return x==st.begin()?--st.end():--x;}
set<node>::iterator SUC(set<node>::iterator x) {return (++x)==st.end()?st.begin():x;}
inline void insert(node x) {
    if(check(x,*suc,*pre,x)<=0) return ; 
    st.insert(x);
    set<node>::iterator cur=st.find(x),i=PRE(cur),j=PRE(i);
    while(check(*cur,*i,*j,*j)>=0) del=i,st.erase(del),i=j,j=PRE(j);
    i=SUC(cur);j=SUC(i);
    while(check(*cur,*i,*j,*j)<=0) del=i,st.erase(del),i=j,j=SUC(j);
}

int main()
{
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>opt[i]>>pot[i].x>>pot[i].y;
		pot[i].x*=3,pot[i].y*=3;
		if(pot[i].y<p0.y||(pot[i].y==p0.y&&pot[i].x<p0.x)) p0=pot[i];
	}
	for(int i=1; i<=3; i++) st.insert(pot[i]);
	for(int i=4; i<=n; i++) {
		if((suc=st.lower_bound(pot[i]))==st.end()) suc=st.begin();
		pre=PRE(suc);
		if(opt[i]==1) insert(pot[i]);
		else if(check(pot[i],*suc,*pre,pot[i])<=0) cout<<"YES\n";
		else cout<<"NO\n";
	} 
	return 0;
}
2021/12/31 13:23
加载中...