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

题目

题目


分析

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


代码

 #include <bits/stdc++.h>
using namespace std; const int maxn=; struct Point
{
int x,y;
double rad;
bool operator < (const Point &rhs) const{
return rad<rhs.rad;
}
}op[maxn],p[maxn]; int n,color[maxn]; bool left(Point A,Point B)
{
return A.x*B.y - A.y*B.x >= ;
} int solve()
{
if(n<=) return ;
int ans=; for(int i=;i<n;i++)
{
int k=; //极角排序
for(int j=;j<n;j++)
if(j!=i)
{
p[k].x=op[j].x-op[i].x;
p[k].y=op[j].y-op[i].y;
if(color[j])
{
p[k].x = -p[k].x; p[k].y = -p[k].y;
}
p[k].rad=atan2(p[k].y , p[k].x);
k++;
}
sort(p,p+k); //滑动
int L= , R= , cnt=;
while(L < k)
{
if(R==L) { R = (R+)%k; cnt++; }
while(R != L && left(p[L] , p[R]))
{
R = (R+)%k; cnt++;
}
cnt--; L++;
ans=max(ans,cnt);
}
}
return ans;
} int main()
{
while(scanf("%d",&n)== && n)
{
for(int i=;i<n;i++)
scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);
printf("%d\n",solve());
}
return ;
}
上一篇:Android 动画深入分析


下一篇:UVA - 1606 Amphiphilic Carbon Molecules (计算几何,扫描法)