首页 > 代码库 > poj 2187

poj 2187

2024-07-07 09:40:19   221人阅读

求凸包后枚举凸包上的点

?
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 100010
#define INF 0x7fffffff
#define inf 100000000
#define MOD 1000000007
#define ULL unsigned long long
#define LL long long
 
using namespace std;
 
const double ESP = 1e-10;
 
double add(double a, double b) {
    if(abs(a+b) < ESP * (abs(a) + abs(b))) return 0;
    return a+b;
}
 
struct P
{
    double x, y;
     
    P() {}
     
    P(double x, double y) : x(x), y(y) {}
     
    P operator - (P p) {
        return P(add(x, -p.x), add(y, -p.y));
    }
 
    P operator + (P p) {
        return P(add(x, p.x), add(y, p.y));
    }
 
    P operator * (double d) {
        return P(x*d, y*d);
    }
 
    double dot(P p) {
        return add(x*p.x, y*p.y);
    }
 
    double det(P p) {
        return add(x*p.y, - y*p.x);
    }
};
 
P ps[maxn];
int n;
 
bool cmp_x(const P& p, const P& q) {
    if(p.x != q.x) return p.x < q.x;
    return p.y < q.y;
}
 
vector<P> convex_full() {
    sort(ps, ps+n, cmp_x);
    int k = 0;
    vector<P> qs(n*2);
    for(int i = 0; i < n; ++ i) {
        while(k > 1 && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0)
            -- k;
        qs[k++] = ps[i];
    }
 
    for(int i = n-2, t = k; i >= 0; -- i) {
        while(k > t && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0)
            -- k;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}
 
double dist(P p, P q) {
    return (p-q).dot(p-q);
}
 
void solve() {
    vector<P> qs = convex_full();
    // printf("%d\n", qs.size());
    double res = 0;
    for(int i = 0; i < (int)qs.size(); ++ i) {
        for(int j = 0; j < i; ++ j) {
            res = max(res, dist(qs[i], qs[j]));
        }
    }
    printf("%.0lf\n", res);
}
 
int main()
{
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i < n; ++ i) {
            scanf("%lf%lf", &ps[i].x, &ps[i].y);
        }
        solve();
    }
    return 0;
}

　　


联系
我们