题目描述：
给你一些长方形（告诉你四个点坐标），每个长方形只可选择其两条对角线中的一条。问你又没有可能存在一种选择方案，使选择的对角线都不相交。
解题报告：
赤裸的2-sat，如果不了解2-sat，请看：
http://blog.sina.com.cn/s/blog_64675f540100k2xj.html
利用到的就是判断线段相交，比如i长方形的1号对角线和j长方形的2号对角线相交，那么连接
i1->j1(表示如果i选1号，那么j只能选1号），构图方法依次类推。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define SIZE 2000 // 点的个数
#define esize 4000000 // 边的个数
int v[SIZE], cnt;
struct edge{int from, to, next;}e[esize];
void insert(int from, int to)
{
e[cnt].from = from, e[cnt].to = to; e[cnt].next =
v[from]; v[from] = cnt++;
}
int index2, dfn[SIZE], low[SIZE], instack[SIZE], sta[SIZE],
top;
int belong[SIZE], cntnum, num[SIZE];
void tarjan(int id)
{
dfn[id]
= low[id] = ++index2;
instack[id] = 1; sta[top++] = id;
int tmp
= v[id];
while(tmp != -1)
{
if (!dfn[e[tmp].to])
{
tarjan(e[tmp].to);
if (low[e[tmp].to] < low[id])
low[id] = low[e[tmp].to];
}
else if (instack[e[tmp].to]
&& dfn[e[tmp].to] <
low[id])
low[id] = dfn[e[tmp].to];
tmp = e[tmp].next;
}
if
(dfn[id] == low[id])
{
do
{
tmp = sta[--top]; instack[tmp] = 0;
belong[tmp] = cntnum;
num[cntnum]++;
}while(tmp != id);
cntnum++;
}
}
bool solve(int n) // n是一半的人数 执行tarjan和topsort,完成标记
{
index2
= cntnum = top = 0;
memset(dfn, 0, sizeof(dfn));
memset(num, 0, sizeof(num));
for(int
i = 0; i < 2 * n; i++)
if (!dfn[i]) tarjan(i);
for(int
i = 0; i < n; i++)
//在缩点的图中标记互斥的缩点。（原来互斥，现在也互斥）
if (belong[i] == belong[i +
n]) return false;
return
true;
}
struct pint
{
double
x, y;
};
int EPS(double xx)
{
if (xx
<= 0.00001 && xx
>= -0.00001) return 0;
else if
(xx > 0) return 1;
else
return -1;
}
double direction(pint p1, pint p2, pint p3)
{
return
(p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y -
p1.y);
}
bool online(pint p1, pint p2, pint p3)
{
return
(p3.x >= min(p1.x, p2.x)
&& p3.x <= max(p1.x,
p2.x) && p3.y >=
min(p1.y, p2.y) && p3.y
<= max(p1.y, p2.y));
}
bool insect(pint p1, pint p2, pint p3, pint p4)
{
double
d1 = direction(p3, p4, p1);
double
d2 = direction(p3, p4, p2);
double
d3 = direction(p1, p2, p3);
double
d4 = direction(p1, p2, p4);
if
(EPS(d1) * EPS(d2) < 0
&& EPS(d3) * EPS(d4)
< 0) return true;
else if
(EPS(d1) == 0 && online(p3, p4,
p1)) return true;
else if
(EPS(d2) == 0 && online(p3, p4,
p2)) return true;
else if
(EPS(d3) == 0 && online(p1, p2,
p3)) return true;
else if
(EPS(d4) == 0 && online(p1, p2,
p4)) return true;
return
false;
}
int n;
pint jeo[1000][4];
bool cmp(pint a, pint b)
{
if (a.y
== b.y) return a.x < b.x;
return
a.y < b.y;
}
int main()
{
while(scanf("%d", &n)
&& n)
{
memset(v, -1, sizeof(v)); cnt
= 0;
for(int i = 0; i
< n; i++)
{
for(int j = 0; j < 4; j++)
scanf("%lf%lf", &jeo[i][j].x,
&jeo[i][j].y);
sort(jeo[i], jeo[i] + 4, cmp);
}
for(int i = 0; i
< n; i++)
for(int j = i + 1; j < n;
j++)
if (i !=
j)
{
if (insect(jeo[i][0],
jeo[i][3], jeo[j][0], jeo[j][3]))
{
insert(i, j + n);
insert(j, i + n);
}
if (insect(jeo[i][0],
jeo[i][3], jeo[j][1], jeo[j][2]))
{
insert(i, j);
insert(j + n, i + n);
}
if (insect(jeo[i][1],
jeo[i][2], jeo[j][0], jeo[j][3]))
{
insert(i + n, j + n);
insert(j, i);
}
if (insect(jeo[i][1],
jeo[i][2], jeo[j][1], jeo[j][2]))
{
insert(i + n , j);
insert(j + n, i);
}
}
if (solve(n))
printf("YES\n");
else printf("NO\n");
}
}
加载中，请稍候......
加载中…
喜欢