首页 > 其他 > 详细

【UVa】1606 Amphiphilic Carbon Molecules(计算几何)

时间:2018-01-20 00:06:35      阅读:216      评论:0      收藏:0      [点我收藏+]

题目

题目

 


分析

跟着lrj学的,理解了,然而不是很熟,还是发上来供以后复习

 


 

代码

技术分享图片
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=1005;
 5 
 6 struct Point
 7 {
 8     int x,y;
 9     double rad;
10     bool operator < (const Point &rhs) const{
11         return rad<rhs.rad;
12     }
13 }op[maxn],p[maxn];
14 
15 int n,color[maxn];
16 
17 bool left(Point A,Point B)
18 {
19     return A.x*B.y - A.y*B.x >= 0;
20 }
21 
22 int solve()
23 {
24     if(n<=2) return 2;
25     int ans=0;
26     
27     for(int i=0;i<n;i++)
28     {
29         int k=0;
30         
31         //极角排序 
32         for(int j=0;j<n;j++)
33             if(j!=i)
34             {
35                 p[k].x=op[j].x-op[i].x;
36                 p[k].y=op[j].y-op[i].y;
37                 if(color[j])
38                 {
39                     p[k].x = -p[k].x; p[k].y = -p[k].y;
40                 }
41                 p[k].rad=atan2(p[k].y , p[k].x);
42                 k++;
43             }
44         sort(p,p+k);
45         
46         //滑动 
47         int L=0 , R=0 , cnt=2;
48         while(L < k)
49         {
50             if(R==L) {  R = (R+1)%k; cnt++;  }
51             while(R != L && left(p[L] , p[R]))
52             {
53                 R = (R+1)%k; cnt++;
54             }
55             cnt--; L++;
56             ans=max(ans,cnt);
57         }
58     }
59     return ans;
60 }
61 
62 int main()
63 {
64     while(scanf("%d",&n)==1 && n)
65     {
66         for(int i=0;i<n;i++)
67             scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);
68         printf("%d\n",solve());
69     }
70     return 0;
71 }
View Code

 

 

【UVa】1606 Amphiphilic Carbon Molecules(计算几何)

原文:https://www.cnblogs.com/noblex/p/8319184.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!