hdu5539 Security Corporation

题意：给定n个直线，保证无三线共点，将点染色，使得相邻两点颜色不同，最小化颜色数量

题解

这个图非常特殊，每个点度数最多为4，所以可以按照(x,y)排序，把两条边定为入边两条定为出边
选择一个点使得他与前两个点颜色不同即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const double eps=1e-8;
int sgn(double x){return (x>eps)-(x<-eps);}

struct P{
	double x,y;
	int id;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
	double len(){return sqrt(x*x+y*y);}
	void read(){scanf("%lf%lf",&x,&y);}
};
bool operator<(P a,P b){
	return sgn(a.x-b.x) ? a.x < b.x : a.y < b.y;
}
P operator+(P a,P b){
	return P(a.x+b.x,a.y+b.y);
}
P operator-(P a,P b){
	return P(a.x-b.x,a.y-b.y);
}
P operator*(P a,double b){
	return P(a.x*b,a.y*b);
}
P operator/(P a,double b){
	return P(a.x/b,a.y/b);
}
double operator*(P a,P b){
	return a.x*b.y-a.y*b.x;
}
double operator^(P a,P b){
	return a.x*b.x+a.y*b.y;
}
double det(P a,P b,P c){
	return (b-a)*(c-a);
}
struct L{
	P a,b;
	P v(){return b-a;}
}l[maxn];
bool parallel(L l1,L l2){
	return sgn(l1.v()*l2.v())==0;
}	
P intersect(L l1,L l2){
	double s1=det(l1.a,l1.b,l2.a);
	double s2=det(l1.a,l1.b,l2.b);
	return (l2.a*s2-l2.b*s1)/(s2-s1);
}
vector<P>vec[maxn];

vector<int>G[maxn*maxn];
int col[maxn*maxn];
int in[maxn*maxn];
int n;
int mex(int x){
	if(!(x>>0&1))return 1;
	if(!(x>>1&1))return 2;
	if(!(x>>2&1))return 4;
	return -1;
}
int main(){
//FBI WARNING!!!!
//freopen("hdu5539.in","r",stdin);
//FBI WARNING!!!!


	int T;
	scanf("%d",&T);	
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			l[i].a.read();
			l[i].b.read();
			vec[i].clear();
		}
		int cur=0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				cur++;
				if(!parallel(l[i],l[j])){
					P p=intersect(l[i],l[j]);
					p.id=cur;
					col[cur]=0;
					in[cur]=0;
					G[cur].clear();
					vec[i].push_back(p);
					vec[j].push_back(p);
					//cout << i << " " << j <<endl;
				}else col[cur]=-1;
			}
		}
		for(int i=1;i<=n;i++)
			sort(vec[i].begin(),vec[i].end());
		for(int i=1;i<=n;i++){
			for(int j=0;j+1<vec[i].size();j++){
				G[vec[i][j].id].push_back(vec[i][j+1].id);
				in[vec[i][j+1].id]++;
				//cerr<<vec[i][j].id <<"->" << vec[i][j+1].id <<endl;
			}
		}
		queue<int>q;
		for(int i=1;i<=cur;i++)
			if(!in[i]&&col[i]!=-1){
				q.push(i);
				col[i]=2;
			}
		while(!q.empty()){
			int u=q.front();q.pop();
			//printf("queue %d\n",u);
			col[u]=mex(col[u]);
			for(int i=0;i<G[u].size();i++){
				int v=G[u][i];
				col[v]|=col[u];
				if(!--in[v])
					q.push(v);
			}
		}
		cur=0;
		int mxc=0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				cur++;
				int ans=-1;
				if(col[cur]==-1)ans=-1;
				else if(col[cur]>>0&1)ans=1;
				else if(col[cur]>>1&1)ans=2;
				else if(col[cur]>>2&1)ans=3;
				mxc=max(mxc,ans);
			}
		}
		
		cur=0;
		printf("%d\n",mxc);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				cur++;
				int ans=-1;
				if(col[cur]==-1)ans=-1;
				else if(col[cur]>>0&1)ans=1;
				else if(col[cur]>>1&1)ans=2;
				else if(col[cur]>>2&1)ans=3;
				printf("%d%c",ans," \n"[j==n]);
			}
		}
	}
	return 0;
}