首页 > 其他 > 详细

Uva 1606

时间:2015-12-24 22:19:22      阅读:336      评论:0      收藏:0      [点我收藏+]

题意:给你平面上n个点,找到一条直线,使得直线一侧的黑点加上直线另一侧的白点数量最大。线上的点可以属于任意一侧。

技术分享
#include<bits/stdc++.h>

using namespace std;
struct Point{
    int x,y;
    int tag;
    double rad;
    bool operator<(const Point &rhs)const{
        return rad<rhs.rad;
    }
};
Point P[1010],tmp[1010];

int cross(const Point &a,const Point &b){
    return a.x*b.y-b.x*a.y;
}

int main(){
    //freopen("in.txt","r",stdin);
    int n;
    while(cin>>n&&n){
        for(int i=0;i<n;i++)
            cin>>P[i].x>>P[i].y>>P[i].tag;

        int ans=0;
        for(int i=0;i<n;i++){
            int k=0;
            for(int j=0;j<n;j++){
                if(i==j) continue;
                tmp[k].x=P[j].x-P[i].x;
                tmp[k].y=P[j].y-P[i].y;
                tmp[k].tag=P[j].tag;
                if(tmp[k].tag){
                    tmp[k].x*=-1;
                    tmp[k].y*=-1;
                }
                tmp[k].rad=atan2(tmp[k].y,tmp[k].x);
                k++;
            }
            sort(tmp,tmp+k);
            int L=0,R=0,cnt=2;
            while(L<k){
                if(R==L){
                    R=(R+1)%k;
                    cnt++;
                }
                while(R!=L&&cross(tmp[L],tmp[R])>=0){
                    R=(R+1)%k;
                    cnt++;
                }
                cnt--;
                L++;
                ans=max(ans,cnt);

            }
        }
        cout<<ans<<endl;
    }
    return 0;

}
View Code

 

Uva 1606

原文:http://www.cnblogs.com/onlyAzha/p/5074399.html

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