Submission #44454043

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int mod=1e9+7;
struct node{
	double x;
	double y;
	int id;
	int col; 
}dot[500005];
const double eps=1e-12;
bool online[500005];
const double pi = acos(-1), pi_2 = 2 * acos(-1);
double check(node a1,node a2,node b1,node b2){
	node A=(node){a2.x-a1.x,a2.y-a1.y,0};
	node B=(node){b2.x-b1.x,b2.y-b1.y,0};
	double tmp=A.x*B.y-A.y*B.x;
	if(fabs(tmp)<eps){
		return 0;
	}
	else{
		return tmp;
	}
}
double dis(node x,node y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
bool cmp(node p1,node p2)//排序函数，这个函数别写错了，要不然功亏一篑 
{
    double tmp=check(dot[1],p1,dot[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(dot[1],p1)<dis(dot[1],p2)) 
		return 1;
    return 0;
}

node s[500005];//模拟栈
int top=0; 
bool pan(node x,node y,node k){//栈头点/栈次点/将要加入的点 ，返回是否要弹出栈头 
	if(check(y,x,x,k)>0){
		return 0;
	}
	else{
		return 1;//在一条线上的暂时视为删除 
	}
}
long long res=0;
queue<int>Q;
void solve() {
    while (Q.size()) Q.pop();//清空 
    int y = 2 * top + 1;//首/尾两端点 
    for (int i = 2 * top; i >= 1; i--) {
        if (s[i].col == 1)
            Q.push(i);
        if (s[i].col == 2)
            y = i;
        while (Q.size() && Q.front() >= i + top) Q.pop();//确定区间在top范围内 
        if (i <= top) {
        	//tx/ty能选就选，否则就只能选左右两个端点 
            int tx = (Q.size()) ? Q.front() : i;
			int ty = (y >= i + top) ? i+top-1 : y;
            if (tx > ty)//不合法选取排除 
                continue;
            res=res+(ty-tx)%mod;//相当于左端点确定颜色后，只要右端点颜色确定，那么整个颜色都可以确定 
        }
    }
}
bool ok1,ok2;
int main(){
//	freopen("constellation.in","r",stdin);
//	freopen("constellation.out","w",stdout);
	ios::sync_with_stdio(false);
	cin >> n;
	double minx=1e10;
	double miny=1e10;
	int minid=1;
	ok1=1;
	ok2=1;
	for(int i=1;i<=n;i++){
		cin >> dot[i].x >> dot[i].y >> dot[i].col;
		if(dot[i].col==1)
            ok2 =0;
        if (dot[i].col==2)
            ok1 =0;
		if(dot[i].y<miny){
			miny=dot[i].y;
			minx=dot[i].x;
			minid=i;
		}
		else if(dot[i].y==miny&&dot[i].x<minx){
			minx=dot[i].x;
			minid=i;
		}
		dot[i].id=i;
	}	
	if(n==1){
		if(dot[1].col!=0){
			cout<<2;
			return 0;
		}
		else{
			cout<<1;
			return 0;
		}
	}
	swap(dot[1],dot[minid]);
	sort(dot+2,dot+1+n,cmp);
	s[1]=dot[1];
	s[2]=dot[2];
	online[dot[1].id]=online[dot[2].id]=1;
	top=2;
	for(int i=3;i<=n;i++){
		while(top>=2&&pan(s[top],s[top-1],dot[i])==1){
			online[s[top].id]=0;
			top--;
		}
		top++;
		s[top]=dot[i];
		online[s[top].id]=1;
	} 
	s[0]=s[top];//先找到整个图的凸包 
	
	for(int i=1;i<=top;i++){//破环成链 
		s[top+i]=s[i];
	}
	solve();
	int tot=0;
	int tot2=0;
	for(int i=1;i<=top;i++){
		tot+=(s[i].col!=1);
		tot2+=(s[i].col!=2);
	}
	if(tot==top){
		res=(res+1)%mod;
	}
	if(tot2==top){
		res=(res+1)%mod;
	}
	for(int i=1;i<=n;i++){
		int id=dot[i].id;
		if(online[id]==0&&dot[i].col==0){
			res=res*2%mod;
		}
	}
	if(ok1){
		res=(res-1)%mod;
	}
	if(ok2){
		res=(res-1)%mod;
	}
	cout<<(res+mod)%mod<<endl;
	
}

Submission Info

Compile Error

./Main.cpp: In function ‘double check(node, node, node, node)’:
./Main.cpp:15:37: warning: missing initializer for member ‘node::col’ [-Wmissing-field-initializers]
   15 |  node A=(node){a2.x-a1.x,a2.y-a1.y,0};
      |                                     ^
./Main.cpp:16:37: warning: missing initializer for member ‘node::col’ [-Wmissing-field-initializers]
   16 |  node B=(node){b2.x-b1.x,b2.y-b1.y,0};
      |                                     ^

Judge Result