覆盖点问题总结(代码片段)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7  
 8 const double eps = 1e-8;
 9  
10 struct node
11     double x,y;
12 ;
13  
14 struct node p[1005],central;
15 double R;
16 int n;
17  
18 double dist(struct node  a,struct node b)
19     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
20 
21  
22  
23 //求外接圆圆心,根据三边相等
24 struct node circumcenter(struct node a,struct node b,struct node c)
25 
26     double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
27     double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
28     double d=a1*b2-a2*b1;
29     struct node tmp;
30     tmp.x = a.x + (c1*b2-c2*b1)/d ;
31     tmp.y = a.y+(a1*c2-a2*c1)/d;
32     return tmp;
33 
34  
35 void min_cover_circle()
36     random_shuffle(p,p+n); 
37     central = p[0];
38     int i,j,k;
39     R=0;
40     for(i=1;i<n;i++)
41         if(dist(central,p[i])+eps>R)
42             central = p[i];
43             R=0;
44             for(j=0;j<i;j++)
45                 if(dist(central,p[j])+eps>R)
46                     central.x=(p[i].x+p[j].x)/2;
47                     central.y=(p[i].y+p[j].y)/2;
48                     R=dist(central,p[j]);
49                     for(k=0;k<j;k++)
50                         if(dist(central,p[k])+eps>R)
51                             central=circumcenter(p[i],p[j],p[k]);
52                             R=dist(central,p[k]);
53                         
54                     
55                 
56             
57         
58     
59 
60  
61  
62 int main()
63     double x,y;
64     while(scanf("%lf%lf%d",&x,&y,&n)!=EOF)
65         int i;
66         for(i=0;i<n;i++)
67             scanf("%lf%lf",&p[i].x,&p[i].y);
68         
69         min_cover_circle();
70         printf("(%.1lf,%.1lf).
%.1lf
",central.x,central.y,R);
71     
72     return 0;
73 

 1 /*
 2 参考：http://blog.sina.com.cn/s/blog_64675f540100sehz.html
 3 题意：给定n个点，找到一个点，使得n个点到这个点的和值最小
 4 模拟退火法
 5 模拟退火的过程
 6 1 找到这些点所在的范围，用两个点框定（代码中e1，e2两个点)
 7 2 在这个范围内生成NUM个点（NUM自定）
 8 3 对于每个生成的点i，在其周围生成NUM个点，一旦有点优于i，则替换。
 9 4 缩小范围D，若D<精度，退出，否则执行 3
10 5 遍历所有NUM个点，找到val的最大值
11 */
12 #include <iostream>
13 #include <cstdio>
14 #include <cstdlib>
15 #include <cmath>
16 #include <cstring>
17 #include <string>
18 #include <algorithm>
19 #include <set>
20 #include<map>
21 #include<ctime>
22 using namespace std;
23 const int NUM=30;
24 const int RAD=1000;
25 struct point
26 
27     double x,y,val;
28     point()
29     point(double _x,double _y):x(_x),y(_y)
30 p[1001],May[NUM],e1,e2;
31 int n;
32 double dis(point a,point b)
33 
34     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
35 
36 double judge(point t)//评价函数，得到点t的评价值val
37 
38     double len=0;
39     for(int i=0;i<n;i++)
40     len=max(len,dis(t,p[i]));
41     return len;
42 
43 double Rand()return rand()%(RAD+1)/(1.0*RAD);//随机产生0-1的浮点数
44 point Rand_point(point a,point b)//在a,b框定的四边形内随机生成点
45 
46     point tmp=point(a.x+(b.x-a.x)*Rand(),a.y+(b.y-a.y)*Rand());
47     tmp.val=judge(tmp);
48     return tmp;
49 
50 void solve(double D)
51 
52     for(int i=0;i<NUM;i++)
53     May[i]=Rand_point(e1,e2);//步骤2
54     while(D>0.01)//步骤 3
55     
56         for(int i=0;i<NUM;i++)
57         for(int j=0;j<NUM;j++)
58         
59             point tmp=Rand_point(point(May[i].x-D,May[i].y-D),point(May[i].x+D,May[i].y+D));
60             if(tmp.val<May[i].val)
61             
62                 May[i]=tmp;
63             
64         
65         D*=0.5;
66     
67     point ans;
68     ans.val=1LL<<45;
69     for(int i=0;i<NUM;i++)
70     if(May[i].val<ans.val)
71     ans=May[i];
72     printf("(%.1f,%.1f).
",ans.x,ans.y);
73     printf("%0.1f
",ans.val);
74 
75 int main()
76 
77     srand(time(0));
78     e2=point(0,0);
79     while(scanf("%lf%lf%d",&e1.x,&e2.y,&n)!=EOF)
80     
81         for(int i=0;i<n;i++)
82         
83         scanf("%lf%lf",&p[i].x,&p[i].y);
84         e1.x=min(e1.x,p[i].x);//框定初始范围
85         e1.y=min(e1.y,p[i].y);
86         e2.x=max(e2.x,p[i].x);
87         e2.y=max(e2.y,p[i].y);
88         
89         solve(max(e2.y-e1.y,e2.x-e1.x));
90     
91 

 1 #include <stdio.h>
 2 #define ARRAY_SIZE 100
 3 struct Point 
 4     int x;
 5     int y;
 6 ;
 7 struct Point p[ARRAY_SIZE];
 8 int main(void) 
 9     int i, n;
10     int min_x, max_x, min_y, max_y;
11     scanf("%d", &n);
12     for(i = 0; i < n; ++i)
13         scanf("%d%d", &p[i].x, &p[i].y);
14     min_x = max_x = p[0].x;
15     min_y = max_y = p[0].y;
16     for(i = 1; i < n; ++i) 
17         if(min_x > p[i].x)
18             min_x = p[i].x;
19         if(max_x < p[i].x)
20             max_x = p[i].x;
21         if(min_y > p[i].y)
22             min_y = p[i].y;
23         if(max_y < p[i].y)
24             max_y = p[i].y;
25     
26     printf("%d %d %d %d
", min_x, min_y, max_x, max_y);
27     return 0;
28