In The End

个人博客

0%

UVA1606题：两亲性分子（极角排序+平面扫描）

发表于 更新于 分类于 ，

这道题目是我前面讲过的极角排序的一道应用（不了解叉积和极角排序的可以看我前一篇博客），但是难度大的地方并不在于极角排序而在于后面的平面扫描，所以这并不是一道裸题，但是希望喜欢思考和喜欢几何的同学可以去试一下这道题

代码（使用atan2函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1010;

struct point{
    int x,y,color;
    double angle;
    void input(){
        cin>>x>>y>>color;
    }
};

point s[maxn],v[maxn];

int det(const point a,const point b){
    return a.x*b.y-a.y*b.x;
}

int main(){
    int n,ans;
    while(cin>>n&&n){
        ans=0;
        for(int i=0;i<n;i++)
            s[i].input();
        for(int i=0;i<n;i++){
            int k=0;
            for(int j=0;j<n;j++){
                if(i!=j){
                    v[k].x=s[j].x-s[i].x;
                    v[k].y=s[j].y-s[i].y;
                    if(s[j].color){
                        v[k].y=-v[k].y;
                        v[k].x=-v[k].x;
                    }
                    v[k].angle=atan2(v[k].y,v[k].x);
                    k++;
                }
            }
            sort(v,v+k,[](point a,point b){return a.angle<b.angle;});
            int left=0,right=0,sum=2;
            while(left<k){
                if(left==right){
                    right=(left+1)%k;
                    sum=2;
                }
                while(left!=right&&det(v[left],v[right])>=0){
                    right=(right+1)%k;
                    sum++;
                }
                ans=max(ans,sum);
                sum--;
                left++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

代码（纯粹使用二维叉积）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1010;

struct point{
    int x,y,color;
    void input(){
        cin>>x>>y>>color;
    }
};

point s[maxn],v[maxn];

int det(const point a,const point b){
    return a.x*b.y-a.y*b.x;
}

bool compare(const point a,const point b){
    if(det(a,b)==0)
        return a.x<b.x;
    else
        return det(a,b)>0;
}

int main(){
    int n,ans;
    while(cin>>n&&n){
        ans=0;
        for(int i=0;i<n;i++)
            s[i].input();
        for(int i=0;i<n;i++){
            int k=0;
            for(int j=0;j<n;j++){
                if(i!=j){
                    v[k].x=s[j].x-s[i].x;
                    v[k].y=s[j].y-s[i].y;
                    if(s[j].color){
                        v[k].y=-v[k].y;
                        v[k].x=-v[k].x;
                    }
                    k++;
                }
            }
            sort(v,v+k,compare);
            int left=0,right=0,sum=2;
            while(left<k){
                if(left==right){
                    right=(left+1)%k;
                    sum=2;
                }
                while(left!=right&&det(v[left],v[right])>=0){
                    right=(right+1)%k;
                    sum++;
                }
                ans=max(ans,sum);
                sum--;
                left++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}