题目描述
Linköping有一个相当复杂的水资源运输系统。在Linköping周围的出水点有一些水井。这些水通过管道输送到其它地点。每条管道是从某一个水井到城市的某个位置的直线管道。
所有管道在地下的深度相同。因此，无论何时，两个管道相交时，它们会形成交点。幸运的是，管道系统正好是以满足两个管道有交点的方式建造。井不计入交点。任何数量的管道（包括零个与超过两个）都可以来源于每一个水井。
这些交点导致了一个问题，因为污垢（石灰和其它东西的混合物）往往会卡住交点，导致管道崩溃和坍塌，导致大型水槽孔的形成。这样的水槽孔对Linköping的学生有吸引的效果，使他们荒废学业，不受教育，这从长远来看将不只是导致管道系统的崩溃，还有社会的结构。因此，当务之急是管道定期清理。北欧提水再分配公司（NWERC） -负责Linköping的水管的 – 拥有充足的机器人车队才可以完成此任务。一个机器人可以在一条管道的开始位置被插入。然后，机器人通过管道一直到结束，并清除沿途所有交点。到达终点后，机器人转身并返回它开始的井。为了防止机器人互相碰撞，*法规规定每当两个管相交，它们中的至多一个可以包含一个机器人。
由于整个水系统在被清洁时必须关闭（另一*法规），则NWERC想迅速完成清洗，使用一批次清洁机器人，都必须在同一时间开始。
你的任务是验证是否可以做到这一点 - 即，是否能够把机器人同时插入管道中的一些，在不会有两个机器人相撞的危险下清洁所有交点。
输入格式
输入包括：
第一行两个整数w(1<=w<=1000)和p(1<=p<=1000)，分别表示井的数量和管道的数量。
接下来w行，每行两个整数xi和yi（-10000<=x,y<=10000），表示i号井的位置（井从1到w编号）。
接下来p行，每行3个整数s（1<=s<=w）表示管道从s号井开始，x和y（-10000<=x,y<=10000）表示管道在位置为x，y的点结束。
每条管道都有一个井，就是它开始的那个。被两个或多个管道共享的点是一口井。任两条管道至多会有一个交点。两条管道的公共点可以是他们其中之一或两者的端点。所有管道的长度为正数。
输出格式
If it is possible to clean all intersections as described above, output “possible”. Otherwise, output “impossible”.
如果在上述情况下可以清理所有交点，输出“possible”，否则输出“impossible”。
-
题解：
- 题目意思一些射线，端点不算交点，相交的射线只能放一个机器人，问是否有方案让每一个交点都被机器人经过；
- 如果A和B有交点，那么A放B不放，A不放B一定放，（多个交于一点也是符合题意的），转化成2-sat求解；
- 翻阅了官解，发现如果有交点A和B连边，二分图判定（因为合法的方案对应了二分图的某一边的点集）；
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n,m,tot,id[N][],o=,hd[N<<],dfn[N<<],low[N<<],idx,st[N<<],top,bl[N<<],del[N<<],cnt;
struct Edge{int v,nt;}E[N*N*];
struct point{
int x,y;
point(int _x=,int _y=):x(_x),y(_y){};
point operator +(const point&A)const{return point(x+A.x,y+A.y);}
point operator -(const point&A)const{return point(x-A.x,y-A.y);}
bool operator ==(const point&A)const{return x==A.x&&y==A.y;}
int operator *(const point&A)const{return x*A.x+y*A.y;}
int operator ^(const point&A)const{return x*A.y-y*A.x;}
}p[N];
struct line{point a,b;}l[N];
void Adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
void tarjan(int u){
dfn[st[++top]=u]=low[u]=++idx;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(!del[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v;cnt++;
do{
bl[v=st[top--]]=cnt;
del[v]=;
}while(v!=u);
}
}
bool judge(int i,int j){
if(l[i].a==l[j].a)return false;
point a=l[j].a-l[i].a,b=l[j].b-l[i].a,c=l[i].b-l[i].a;
if((ll)(c^a)*(c^b)>)return false;
b=l[j].a-l[i].b,c=l[j].b-l[j].a;
if((ll)(c^a)*(c^b)>)return false;
return true;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bzoj4427.in","r",stdin);
freopen("bzoj4427.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(int i=,x;i<=m;i++){
scanf("%d",&x);l[i].a=p[x];
scanf("%d%d",&l[i].b.x,&l[i].b.y);
id[i][]=++tot;id[i][]=++tot;
}
for(int i=;i<=m;i++)
for(int j=i+;j<=m;j++)if(i!=j&&judge(i,j)){
Adde(id[i][],id[j][]);
Adde(id[i][],id[j][]);
Adde(id[j][],id[i][]);
Adde(id[j][],id[i][]);
}
for(int i=;i<=tot;i++)if(!dfn[i])tarjan(i);
int fg=;for(int i=;i<=m;i++)if(bl[id[i][]]==bl[id[i][]]){fg=;break;}
puts(fg?"impossible":"possible");
return ;
}bzoj4427