2010-02-03.ural1065-pku1758
這個(gè)題還是比較有意思的。
題目是要求在一個(gè)凸多邊形中選幾個(gè)點(diǎn)，要保證新組成的多邊形包含m個(gè)景觀點(diǎn)
題目中給出的凸多邊形是按照順時(shí)針順序給出的，我們可以按照順序找到合法的點(diǎn)的連接方法，然后轉(zhuǎn)換成圖論模型。
首先將題目中給出的點(diǎn)拷貝一份
p[0...n-1] 存的是原始的順時(shí)針順序給出的點(diǎn)
p[n...2n-1]是對(duì)上邊的拷貝
然后
for (i = 0;i < n;i++) {
for (j = 1;j < n;j++) {
判斷由p[i...i+j]組成的多變形是否包含景點(diǎn)。
其實(shí)也就是線段<p[i],p[j]> 是否有景點(diǎn)在左側(cè)。
}
}
建圖之后，由于點(diǎn)最多只有50個(gè)，完全可以用floyd求出所有點(diǎn)之間的最短距離，然后再枚舉三角形
求出一個(gè)最短距離即可。
注意不能直接用floyd求出來的值dis[i][i]來找最短距離，因?yàn)闀?huì)產(chǎn)生面積等于零的情況。
1
2 /*
3 * SOUR:ural1065 pku1758
4 * ALGO:computational and graph theory
5 * DATE:2010年 02月 01日 星期一 15:38:51 CST
6 * COMM:5//http://www.shnenglu.com/schindlerlee/
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 #include<cmath>
14 using namespace std;
15 typedef long long LL;
16 const int maxint = 0x7fffffff;
17 const long long max64 = 0x7fffffffffffffffll;
18 /*#define fprintf(x
) while(0)*/
19 const int N = 128;
20 const int M = 2048;
21 int n,m, g[N][N];
22 struct point_t{
23 int x,y;
24 point_t(){}
25 point_t(int a,int b){x = a,y = b;}
26 }p[N],monu[M];
27 double dis[N][N];
28 point_t operator + (point_t a,point_t b) { return point_t(a.x + b.x,a.y + b.y);}
29 point_t operator - (point_t a,point_t b) { return point_t(a.x - b.x,a.y - b.y);}
30 int cross_mul(point_t a,point_t b) { return a.x * b.y - a.y * b.x;}
31 int dot_mul(point_t a,point_t b) { return a.x * b.x + a.y * b.y;}
32
33 bool judge(int beg,int end)
34 {
35 int i,j;
36 for (i = 0;i < m;i++) {
37 if (cross_mul(p[end]-p[beg],monu[i]-p[beg]) >= 0) {
38 return false;
39 }
40 }
41 return true;
42 }
43
44 void ckmin(double &a,double b) { if (a > b) { a = b; } }
45 #define sqr(x) ((x)*(x))
46 double dist(const point_t &a,const point_t &b) { return sqrt(0.0 + sqr(a.x-b.x) + sqr(a.y-b.y)); }
47
48 int main()
49 {
50 int i,j,k;
51 scanf("%d%d",&n,&m);
52 for (i = 0;i < n;i++) { scanf("%d %d",&p[i].x,&p[i].y); p[i+n] = p[i]; }
53 for (i = 0;i < m;i++) { scanf("%d %d",&monu[i].x,&monu[i].y); }
54 for (i = 0;i < n;i++) {
55 for (j = 1;j < n;j++) {
56 if (judge(i,i+j)) {
57 g[i][(i+j)%n] = 1;
58 }
59 }
60 }
61
62 for (i = 0;i < n;i++) {
63 for (j = 0;j < n;j++) {
64 if (g[i][j]) {
65 dis[i][j] = dist(p[i],p[j]);
66 }else if(i == j){
67 dis[i][j] = 0;
68 }else {
69 dis[i][j] = maxint;
70 }
71 }
72 }
73
74 //floyd
75 for (k = 0;k < n;k++) {
76 for (i = 0;i < n;i++) {
77 for (j = 0;j < n;j++) {
78 ckmin(dis[i][j],dis[i][k]+dis[k][j]);
79 }
80 }
81 }
82
83 //這么寫完全是為了保證面積不為0
84 double res = maxint;
85 for (k = 0;k < n;k++) {
86 for (i = 0;i < n;i++) {
87 for (j = 0;j < n;j++) {
88 if (res > dis[i][j] + dis[j][k] + dis[k][i] && cross_mul(p[i]-p[k],p[j]-p[k]) != 0) {
89 res = dis[i][j] + dis[j][k] + dis[k][i];
90 }
91 }
92 }
93 }
94
95 printf("%.2f\n",res);
96 return 0;
97 }
98