[几何] [2847] How Far Can We Go 第七次训练赛 相关搜索: Can, Far, How, 训练

GDUT_CHC

凸包 + 随机投点 （标准算法应该是 凸包 + 旋转卡壳）

没什么好说，先求出凸包，然后随机投点。投啊投，就AC了

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <cmath>
   
4. #include <string>
   
5. #include <set>
   
6. #include <queue>
   
7. #include <map>
   
8. using namespace std;
   
9. 
   
10. #define MAXN 100011
    
11. #define eps 1e-8
    
12. 
    
13. struct point { double x, y; };
    
14. 
    
15. point p[MAXN];
    
16. int stack[MAXN];
    
17. point s;
    
18. 
    
19. bool zero(double x) { return ((x)>0?(x):-(x))<eps;}
    
20. 
    
21. double dist(point a, point b)
    
22. {
    
23.     double p = a.x - b.x, q = a.y - b.y;
    
24.     return p*p + q*q;
    
25. }
    
26. 
    
27. double xmult(point a, point b, point c)
    
28. {
    
29.     return   (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y) ;
    
30. }
    
31. 
    
32. bool cmp(point a, point b)
    
33. {
    
34.     double t = xmult(s, a, b);
    
35.     if (!zero(t)) return t < 0;
    
36.     return dist(s, a) > dist(s, b);
    
37. }
    
38. 
    
39. int graham(int n)
    
40. {
    
41.         int i;
    
42.        
    
43.         for(i=1;i<n;i++)
    
44.         {
    
45.                 if( p[ i ].y<p[0].y ||( p[ i ].y==p[0].y && p[ i ].x<p[0].x ))
    
46.                         swap(p[ i ],p[0]);
    
47.         }
    
48.        
    
49.         s=p[0];
    
50.         sort(p+1,p+n,cmp);
    
51.         stack[0]=0;
    
52.         stack[1]=1;
    
53.        
    
54.         int slip=2;
    
55.         double t;
    
56.         for(i=2;i<n;i++)
    
57.         {
    
58.                 t=xmult(p[0], p[i-1], p[ i ]);
    
59.                 if(zero(t))continue;
    
60.                 while (xmult(p[stack[slip-2]], p[stack[slip-1]], p[ i ]) >0) slip--;
    
61.                
    
62.                 stack[slip]=i;
    
63.                 slip++;
    
64.         }
    
65.         return slip;
    
66. }
    
67. 
    
68. int main()
    
69. {
    
70.         //freopen("test.txt","r",stdin);
    
71.         int n, i, j, all, time;
    
72.         double temp, ans;
    
73.         while(scanf("%d", &n) != EOF && n != 0)
    
74.         {
    
75.                 for(i=0; i<n; i++)
    
76.                         scanf("%lf %lf", &p[ i ].x, &p[ i ].y);
    
77.                
    
78.                 all = graham ( n );
    
79.                
    
80.                 if(ans < 100)time = all * 10;
    
81.                 else time = all * 30;
    
82.                 ans = 0;
    
83.                 while(time--)
    
84.                 {
    
85.                         i = rand()%all;
    
86.                         j = rand()%all;
    
87.                         temp = dist (p[stack[ i ]], p[stack[j]]);
    
88.                         if(temp > ans)
    
89.                                 ans = temp;
    
90.                 }
    
91.                
    
92.                 printf("%.2lf\n", sqrt(ans));
    
93.         }
    
94.        
    
95.        
    
96.         return 0;
    
97. }
    
98. 
    
99. /*Power By GDUT_CHC*/

复制代码

DieIng

拜仁拜仁

不知道何为“旋转卡壳”

DieIng

三鲜

旋转卡壳过啦 嘿嘿 1.08秒 原来少考虑了1个小概率事件下的1个点

GDUT_CHC

旋转卡壳也这么慢 ， 那么那些0.20的是如何做到的？