JOISC 2012 Day2 T2「星座」详解

前言：

字有点多，如果您无法耐心，请您划开。

别人的详解三行就结束了......，导致我一个早上的自闭，所以我将我的理解来给大家分享。

其实这道题很考思想，代码实现则考能力（求解方案数的函数很难想到）。

题目简述：

给你几个红色点/蓝色点/无色点。

对于无色点，它被涂成红色或者蓝色的情况下，它合法当且仅当他能和同色点共同生成一棵树（和原来的同色点能够互相抵达），并且和异色点生成的树没有边相交。（注：存在一棵树即可合法）

题目思路：

引入：

众所周知，世界上有个东西叫做凸包，凸包中又有个东西叫做三角剖分。

凸包明白吧，是一个凸多边形。

三角剖分的话就是在这个凸多边形内部选择一个点，然后将这个点和多边形顶点连线，最终得到很多个三角形。

三角形呢，也是一个凸多边形呢。

所以说只要一个凸多边形内有点，就可以一直三角划分。

题目思路引导：

为什么我们应该想到凸包？因为我们想到了三角划分。

为什么我们应该想到三角划分？

看一下三角划分：某一个三角形内部的点和这个三角形的任意一个顶点连线，总是不会有线段交叉的。

于是假设我们三角划分到了最终不可划分的地步，让我们想想可能会出现哪些情况。

1. 三个颜色相同的点（设为黑色点）的大三角形，中间有一个白色的点，我们令其为 $S$。可能你会想到：要是这个三角形外部还有一个白点，不就寄了吗，其实不然，因为这个颜色相同点组成的三角形，去掉任意一条边还是联通的，那么不论这个在三角形外面的白色的点在内部 $S$ 点哪一个方向，我都可以通过删除一条边连出去完成题目条件。那么拓展一下，要是有两个白点在外面，并且连线后将会经过不同的边呢？这时我们可以先去掉一条，然后先连上一个白点，此时可以将这两个白点共同看作一个点，但是被更大的几何图形包围，这时的处理其实和三角形差不多了。用一个形象的比喻来感性解释，你和两个同伴关在三个不同的牢房，你们想要聚集到一起，且你们手上都有一把搞子（用一次）。显然我可以先和一个同伴汇合，再用他的镐子和另外一个人汇合。但这样不一定能成功，（可以看第三点解释）。

2. 由不同的点组成的三角形包裹一个点，那么很显然此时可以直接将中间的这个点与三角形上颜色相同的点进行连接，很显然这种边不会形成任何交叉，是最理想的一种连边方式。

3. 进行拓展：我们对三角形情况进行拓展，将其看成一个几何图形（凸的），里面包含了很多个点。先简单点，假设里面没有点了，那么我一定合法吗，答案是不一定。读者可以自己画一个正五边形，点分别是白，白，黑白，黑。发现这样的情况肯定是不合法的，因为我黑色点将一个白色点进行了拦截。这样一定会相交导致不合法。但是我们可以发现，要是只存在两个段，一段为白，另一段为黑，他们就不会发生拦截的情况。那么如果没有拦截的话，我就肯定可以成立。现在进一步拔高：里面有各种颜色的点。显然我可以进行三角划分然后进一步解喽，而显然三角划分后都能合法了。

4. 进行总结：我们发现，对于一个三角形而言，不管内部的点数量为多少，颜色是什么，都可以满足题目条件。对于一个多边形而言，不管内部点数量为多少，颜色是什么，只要不出现拦截情况，都可以成立。很显然三角形也是个多边形，因此题目就相当于：给你一个凸包，要求这个凸包不出现拦截情况，求方案数。

5. 进行简化：拦截显然是很困难的想法，我们要进行简化，很显然，出现拦截就代表着（在环上）颜色的分段大于等于三。换句话说，我这个环最多只能出现两种颜色段，那么破环成链后，最多只能出现三个颜色段。求这样构造的方案数。

6. 小贴士：最后别忘了，在凸包内部的点的颜色是任意的，所以别忘了最后乘上 $2^{siz}$ ,其中 $siz$ 是不在凸包上，但是颜色未定的点的数量。

   题目算法引导

7. 我们首先肯定要得到凸包，这里用的 $graham$ 算法，具体的话可以搜索“二维凸包”板子题去看看题解，这里就不再赘述了。

8. 我们该如何求方案数，我认为这是此题的难点（因为是一个 $dalao$ 的想法）。首先，倍长和破环成链是跑不脱的。其次，我们尝试找左端点，假设我的左端点已经确定，并且颜色也是一定的（就假设都是白吧），如果右端点处是个黑色，那么此时我的方案数就是这段区间的长度（每个区域内的点都可以成为颜色转变瞬间的那个点，而要是我颜色转变的位置确定了，我这个区间也就确定了。具体实现还是看看 $solve()$ 吧。

其他坑点：

最后面别忘了换行 $endl$

更多经验:

可以去看看CF 1045E ,这个还要求输出具体方案，我没做，有亿点难。

ac代码：

actcoder:https://atcoder.jp/contests/joisc2012/submissions/44454043

#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;
	
}