2013
12-23

# Another Convex Polygon Problem

You are given a convex polygon with N vertices and M straight lines which divide the polygon into several regions. You must compute the number of regions into which the polygon is divided by the straight lines.

The first line of input contains the number T of test cases. The next lines describe the T test cases. The first line of each test case contains two integer numbers, separated by one blank: the number N of vertices of the convex polygon (3 <= N <= 10) and the number M of straight lines (0 <= M <= 10). The next N lines contain 2 integer numbers X and Y, denoting the coordinates of some vertex of the polygon. The vertices are given in clockwise or anti-clockwise order. Each of the next M lines contains 4 integer numbers: x1 y1 x2 y2. (x1,y1) and (x1,y1) are two different points on the straight line. All the X and Y coordinates in the input file are in the range -20…20.

For each test case print a line having the following format: “Number of regions=XXX.”, where XXX is replaced by the number of regions into which the polygon is divided.

2
3 0
0 0
1 1
1 0
3 3
0 0
1 1
1 0
1 2 3 4
1 2 3 4
1 2 3 4

Number of regions=1.
Number of regions=1.

PS 我之所以把抽取最小值的ex_min()单拿出来是因为这样容易用堆优化。

/*
* hdu-1863
* mike-w
* 2012-4-13
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 128
#define INF (2<<25)
#define min(x,y) ((x)>(y)?(y):(x))

int dst[MAX_SIZE];
int tag[MAX_SIZE];
int f[MAX_SIZE][MAX_SIZE];
int N,M;

int ex_min(void)
{
int i,x;
for(x=-1,i=1;i<=M;i++)
if(!tag[i] && dst[i]<INF)
break;
for(x=i++;i<=M;i++)
if(!tag[i] && dst[i]<dst[x])
x=i;
return x<=M?x:-1;
}

int random_start(void)
{
int i,j;
for(i=1;i<=M;i++)
for(j=1;j<=M;j++)
if(f[i][j]>0)
return i;
return -1;
}

int prim(void)
{
int i,x,cost;
int start=random_start();
if(start==-1)
return -1;
for(i=1;i<=M;i++)
dst[i]=f[start][i],tag[i]=0;
cost=0;
while((x=ex_min())!=-1)
{
tag[x]=1;
cost+=dst[x];
for(i=1;i<=M;i++)
if(!tag[i] && f[x][i]<INF && dst[i]>f[x][i])
dst[i]=f[x][i];
}
for(i=1;i<=M;i++)
if(!tag[i])
cost=-1;
return cost;
}

int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif
int i,j,cost,e1,e2,e3;
while(scanf("%d",&N),N)
{
scanf("%d",&M);
for(i=1;i<=M;i++)
for(j=1;j<=M;j++)
f[i][j]=(i==j?0:INF);
for(i=1;i<=N;i++)
{
scanf("%d%d%d",&e1,&e2,&e3);
f[e1][e2]=f[e2][e1]=min(f[e1][e2],e3);
}
if(N>0)
cost=prim();
else
cost=0;
if(cost==-1)
puts("?");
else
printf("%d\n",cost);
}
return 0;
}

1. 我就是默认下载地址……都30岁的人了，谁翻我电脑看到毛片还要说我？他们只会说“兄弟，我下次U盘拿来了你给我拷几部啊”

2. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)