欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

两亲性分子uva1606

程序员文章站 2022-03-29 21:19:30
...

这个题是我直接转来的原文:

http://blog.csdn.net/u014800748/article/details/43536357

在这我说几句以便理解这个代码,Left函数用来判定是否在分割线的范围内的,还有就是极角相等的点,我开始就是想不通这里的,作者的解法是把这些都放在了p数组中了,再后来的while循环里进行判定就好,这样就做到了循环内饰cnt每次都是加一了。

1.题目描述:点击打开链接

2.解题思路:本题利用极角扫描法解决。极角扫描法的思想是这样的:首先,选择一个点作为基准点,然后求出其他点相对于该基准点的相对坐标,同时求出相对坐标系下的极角。对这些点按照极角由小到大排序。设L=0,R=0,那么每次都以O-p[L]这条线为分隔线,O-p[R]作为扫描线,用cnt来统计在分隔线左侧的点的个数(包括分隔线上的点)。看p[R]这个点是否在分隔线的左侧,如果是,R=(R+1)%k,cnt++。一直让O-p[R]这条扫描线转到刚刚超过180度时候停止,然后L++,cnt--,表示分隔线旋转,原来在分隔线的点成为了分隔线右侧的点了。

不过本题还运用了以下等效的思想,因为统计的是一侧的黑点+另一侧的白点数,不妨在算相对坐标时候把黑点换成白点,并将它旋转180度处理,这样就转化为统计一侧白点的数目了。另一个技巧是判断一个点是否在分隔线左侧利用Cross来判断,不会产生精度问题。

本题选基准点有O(N)种,对点按照极角排序时间是O(NlogN),扫描时候的复杂度是O(N),因此总的时间复杂度是O(N^2logN+N^2)。可以看做O(N^2logN)处理。

3.代码:

  1. //#pragma comment(linker, "/STACK:1024000000,1024000000")  
  2. #include<iostream>  
  3. #include<algorithm>  
  4. #include<cassert>  
  5. #include<string>  
  6. #include<sstream>  
  7. #include<set>  
  8. #include<bitset>  
  9. #include<vector>  
  10. #include<stack>  
  11. #include<map>  
  12. #include<queue>  
  13. #include<deque>  
  14. #include<cstdlib>  
  15. #include<cstdio>  
  16. #include<cstring>  
  17. #include<cmath>  
  18. #include<ctime>  
  19. #include<cctype>  
  20. #include<functional>  
  21. using namespace std;  
  22.   
  23. #define me(s)  memset(s,0,sizeof(s))  
  24. #define rep(i,n) for(int i=0;i<(n);i++)  
  25. typedef long long ll;  
  26. typedef unsigned int uint;  
  27. typedef unsigned long long ull;  
  28. typedef pair <intint> P;  
  29.   
  30. const int N=1000+5;  
  31.   
  32. struct Point  
  33. {  
  34.     int x,y;  
  35.     double rad;  
  36.     bool operator<(const Point&rhs)const  
  37.     {  
  38.         return rad<rhs.rad;  
  39.     }  
  40. }op[N],p[N];  
  41.   
  42. int n,color[N];  
  43.   
  44. bool Left(Point A,Point B)  
  45. {  
  46.     return A.x*B.y-A.y*B.x>=0;  
  47. }  
  48.   
  49. int solve()  
  50. {  
  51.     if(n<=2)return 2;  
  52.     int ans=0;  
  53.   
  54.     for(int i=0;i<n;i++)  //枚举基准点op[i]  
  55.     {  
  56.         int k=0;  
  57.         for(int j=0;j<n;j++)  
  58.             if(j!=i)  
  59.         {  
  60.             p[k].x=op[j].x-op[i].x;  //将其他点都转换为相对坐标  
  61.             p[k].y=op[j].y-op[i].y;  
  62.             if(color[j]){p[k].x=-p[k].x;p[k].y=-p[k].y;} //如果是黑点,将它绕原点旋转180度即可看做白点处理了  
  63.             p[k].rad=atan2(p[k].y,p[k].x);  
  64.             k++;  
  65.         }  
  66.         sort(p,p+k);  
  67.   
  68.         int L=0,R=0,cnt=2;  //分隔线上有2个点  
  69.         while(L<k)  //O-p[L]作为分隔线,O-p[R]作为扫描线,注意,R一直是在0~k-1之间不停地循环着,直到L>=k才停止  
  70.         {  
  71.             if(R==L){R=(R+1)%k;cnt++;}  //空区域,暂时多计入一个点,最后舍去  
  72.             while(R!=L&&Left(p[L],p[R])) //扫描线一直逆时针旋转,直到旋转角度刚刚>180度停止统计  
  73.             {  
  74.                 R=(R+1)%k;  
  75.                 cnt++;  
  76.             }  
  77.             cnt--; //舍去多计入的点,也可以理解为由于分隔线的旋转,原来在分隔线上的点现在变为了右侧的点,要减掉一个  
  78.             L++;   //分隔线旋转  
  79.             ans=max(ans,cnt); //统计这一轮扫描的结果  
  80.         }  
  81.     }  
  82.     return ans;  
  83. }  
  84.   
  85. int main()  
  86. {  
  87.     while(~scanf("%d",&n)&&n)  
  88.     {  
  89.         rep(i,n)  
  90.         scanf("%d%d%d",&op[i].x,&op[i].y,&color[i]);  
  91.         printf("%d\n",solve());  
  92.     }  
  93. }  
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;

#define me(s)  memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;

const int N=1000+5;

struct Point
{
    int x,y;
    double rad;
    bool operator<(const Point&rhs)const
    {
        return rad<rhs.rad;
    }
}op[N],p[N];

int n,color[N];

bool Left(Point A,Point B)
{
    return A.x*B.y-A.y*B.x>=0;
}

int solve()
{
    if(n<=2)return 2;
    int ans=0;

    for(int i=0;i<n;i++)  //枚举基准点op[i]
    {
        int k=0;
        for(int j=0;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;} //如果是黑点,将它绕原点旋转180度即可看做白点处理了
            p[k].rad=atan2(p[k].y,p[k].x);
            k++;
        }
        sort(p,p+k);

        int L=0,R=0,cnt=2;  //分隔线上有2个点
        while(L<k)  //O-p[L]作为分隔线,O-p[R]作为扫描线,注意,R一直是在0~k-1之间不停地循环着,直到L>=k才停止
        {
            if(R==L){R=(R+1)%k;cnt++;}  //空区域,暂时多计入一个点,最后舍去
            while(R!=L&&Left(p[L],p[R])) //扫描线一直逆时针旋转,直到旋转角度刚刚>180度停止统计
            {
                R=(R+1)%k;
                cnt++;
            }
            cnt--; //舍去多计入的点,也可以理解为由于分隔线的旋转,原来在分隔线上的点现在变为了右侧的点,要减掉一个
            L++;   //分隔线旋转
            ans=max(ans,cnt); //统计这一轮扫描的结果
        }
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        rep(i,n)
        scanf("%d%d%d",&op[i].x,&op[i].y,&color[i]);
        printf("%d\n",solve());
    }
}


这个题是我直接转来的原文:

http://blog.csdn.net/u014800748/article/details/43536357

在这我说几句以便理解这个代码,Left函数用来判定是否在分割线的范围内的,还有就是极角相等的点,我开始就是想不通这里的,作者的解法是把这些都放在了p数组中了,再后来的while循环里进行判定就好,这样就做到了循环内饰cnt每次都是加一了。

1.题目描述:点击打开链接

2.解题思路:本题利用极角扫描法解决。极角扫描法的思想是这样的:首先,选择一个点作为基准点,然后求出其他点相对于该基准点的相对坐标,同时求出相对坐标系下的极角。对这些点按照极角由小到大排序。设L=0,R=0,那么每次都以O-p[L]这条线为分隔线,O-p[R]作为扫描线,用cnt来统计在分隔线左侧的点的个数(包括分隔线上的点)。看p[R]这个点是否在分隔线的左侧,如果是,R=(R+1)%k,cnt++。一直让O-p[R]这条扫描线转到刚刚超过180度时候停止,然后L++,cnt--,表示分隔线旋转,原来在分隔线的点成为了分隔线右侧的点了。

不过本题还运用了以下等效的思想,因为统计的是一侧的黑点+另一侧的白点数,不妨在算相对坐标时候把黑点换成白点,并将它旋转180度处理,这样就转化为统计一侧白点的数目了。另一个技巧是判断一个点是否在分隔线左侧利用Cross来判断,不会产生精度问题。

本题选基准点有O(N)种,对点按照极角排序时间是O(NlogN),扫描时候的复杂度是O(N),因此总的时间复杂度是O(N^2logN+N^2)。可以看做O(N^2logN)处理。

3.代码:

  1. //#pragma comment(linker, "/STACK:1024000000,1024000000")  
  2. #include<iostream>  
  3. #include<algorithm>  
  4. #include<cassert>  
  5. #include<string>  
  6. #include<sstream>  
  7. #include<set>  
  8. #include<bitset>  
  9. #include<vector>  
  10. #include<stack>  
  11. #include<map>  
  12. #include<queue>  
  13. #include<deque>  
  14. #include<cstdlib>  
  15. #include<cstdio>  
  16. #include<cstring>  
  17. #include<cmath>  
  18. #include<ctime>  
  19. #include<cctype>  
  20. #include<functional>  
  21. using namespace std;  
  22.   
  23. #define me(s)  memset(s,0,sizeof(s))  
  24. #define rep(i,n) for(int i=0;i<(n);i++)  
  25. typedef long long ll;  
  26. typedef unsigned int uint;  
  27. typedef unsigned long long ull;  
  28. typedef pair <intint> P;  
  29.   
  30. const int N=1000+5;  
  31.   
  32. struct Point  
  33. {  
  34.     int x,y;  
  35.     double rad;  
  36.     bool operator<(const Point&rhs)const  
  37.     {  
  38.         return rad<rhs.rad;  
  39.     }  
  40. }op[N],p[N];  
  41.   
  42. int n,color[N];  
  43.   
  44. bool Left(Point A,Point B)  
  45. {  
  46.     return A.x*B.y-A.y*B.x>=0;  
  47. }  
  48.   
  49. int solve()  
  50. {  
  51.     if(n<=2)return 2;  
  52.     int ans=0;  
  53.   
  54.     for(int i=0;i<n;i++)  //枚举基准点op[i]  
  55.     {  
  56.         int k=0;  
  57.         for(int j=0;j<n;j++)  
  58.             if(j!=i)  
  59.         {  
  60.             p[k].x=op[j].x-op[i].x;  //将其他点都转换为相对坐标  
  61.             p[k].y=op[j].y-op[i].y;  
  62.             if(color[j]){p[k].x=-p[k].x;p[k].y=-p[k].y;} //如果是黑点,将它绕原点旋转180度即可看做白点处理了  
  63.             p[k].rad=atan2(p[k].y,p[k].x);  
  64.             k++;  
  65.         }  
  66.         sort(p,p+k);  
  67.   
  68.         int L=0,R=0,cnt=2;  //分隔线上有2个点  
  69.         while(L<k)  //O-p[L]作为分隔线,O-p[R]作为扫描线,注意,R一直是在0~k-1之间不停地循环着,直到L>=k才停止  
  70.         {  
  71.             if(R==L){R=(R+1)%k;cnt++;}  //空区域,暂时多计入一个点,最后舍去  
  72.             while(R!=L&&Left(p[L],p[R])) //扫描线一直逆时针旋转,直到旋转角度刚刚>180度停止统计  
  73.             {  
  74.                 R=(R+1)%k;  
  75.                 cnt++;  
  76.             }  
  77.             cnt--; //舍去多计入的点,也可以理解为由于分隔线的旋转,原来在分隔线上的点现在变为了右侧的点,要减掉一个  
  78.             L++;   //分隔线旋转  
  79.             ans=max(ans,cnt); //统计这一轮扫描的结果  
  80.         }  
  81.     }  
  82.     return ans;  
  83. }  
  84.   
  85. int main()  
  86. {  
  87.     while(~scanf("%d",&n)&&n)  
  88.     {  
  89.         rep(i,n)  
  90.         scanf("%d%d%d",&op[i].x,&op[i].y,&color[i]);  
  91.         printf("%d\n",solve());  
  92.     }  
  93. }  
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;

#define me(s)  memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;

const int N=1000+5;

struct Point
{
    int x,y;
    double rad;
    bool operator<(const Point&rhs)const
    {
        return rad<rhs.rad;
    }
}op[N],p[N];

int n,color[N];

bool Left(Point A,Point B)
{
    return A.x*B.y-A.y*B.x>=0;
}

int solve()
{
    if(n<=2)return 2;
    int ans=0;

    for(int i=0;i<n;i++)  //枚举基准点op[i]
    {
        int k=0;
        for(int j=0;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;} //如果是黑点,将它绕原点旋转180度即可看做白点处理了
            p[k].rad=atan2(p[k].y,p[k].x);
            k++;
        }
        sort(p,p+k);

        int L=0,R=0,cnt=2;  //分隔线上有2个点
        while(L<k)  //O-p[L]作为分隔线,O-p[R]作为扫描线,注意,R一直是在0~k-1之间不停地循环着,直到L>=k才停止
        {
            if(R==L){R=(R+1)%k;cnt++;}  //空区域,暂时多计入一个点,最后舍去
            while(R!=L&&Left(p[L],p[R])) //扫描线一直逆时针旋转,直到旋转角度刚刚>180度停止统计
            {
                R=(R+1)%k;
                cnt++;
            }
            cnt--; //舍去多计入的点,也可以理解为由于分隔线的旋转,原来在分隔线上的点现在变为了右侧的点,要减掉一个
            L++;   //分隔线旋转
            ans=max(ans,cnt); //统计这一轮扫描的结果
        }
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        rep(i,n)
        scanf("%d%d%d",&op[i].x,&op[i].y,&color[i]);
        printf("%d\n",solve());
    }
}