Beauty Contest
Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.
Input
* Line 1: A single integer, N
* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm
Output
* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.
Sample Input
4
0 0
0 1
1 1
1 0
Sample Output
2
Hint
Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)
Source
题目类型：平面最远点对(凸包+旋转卡壳)
算法分析：易知平面最远点对一定在凸包上，所以先求解凸包，然后使用旋转卡壳更新最远点距离即可，注意这里所有的运算都是整数运算，不要使用double！！！
|
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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
/************************************************* Author :supermaker Created Time :2016/1/27 15:35:39 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 6e4 + 66; struct Point { int x, y; Point () {} Point (int xx, int yy) : x (xx), y (yy) {} Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } int operator ^ (const Point &a) const { return x * a.y - y * a.x; } int operator * (const Point &a) const { return x * a.x + y * a.y; } }; Point p[maxn], pp[maxn]; int n, len; stack <int> sta; int Dist2 (Point p1, Point p2) { return (p2 - p1) * (p2 - p1); } bool polarcmp (Point p1, Point p2) { int tt = (p1 - p[1]) ^ (p2 - p[1]); if (tt > 0) return true; else if (tt == 0 && Dist2 (p1, p[1]) - Dist2 (p2, p[1]) <= 0) return true; return false; } void Garham () { Point start = p[1]; int start_pos = 1; for (int i = 1; i <= n; i++) if (p[i].x - start.x < 0 || (p[i].x - start.x == 0 && p[i].y - start.y < 0)) start = p[i], start_pos = i; swap (p[start_pos], p[1]); sort (p + 2, p + n + 1, polarcmp); while (!sta.empty ()) sta.pop (); if (n == 1) sta.push (1); else if (n == 2) sta.push (1), sta.push (2); else { sta.push (1), sta.push (2); for (int i = 3; i <= n; i++) { while (sta.size () >= 2) { int tt1 = sta.top (); sta.pop (); int tt2 = sta.top (); sta.pop (); if (((p[tt1] - p[tt2]) ^ (p[i] - p[tt2])) <= 0) sta.push (tt2); else { sta.push (tt2), sta.push (tt1); break; } } sta.push (i); } } } int RotatingCalipers () { int res = 0, cur = 1; Point t; for (int i = 0; i < len; i++) { t = pp[i] - pp[(i+1)%len]; while ((t ^ (pp[(cur+1)%len] - pp[cur])) < 0) cur = (cur + 1) % len; res = max (res, max (Dist2 (pp[i], pp[cur]), Dist2 (pp[(i+1)%len], pp[(cur+1)%len]))); } return res; } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 1; i <= n; i++) scanf ("%d%d", &p[i].x, &p[i].y); Garham (); len = sta.size (); int pos = len - 1; while (!sta.empty ()) { int cur = sta.top (); sta.pop (); pp[pos--] = p[cur]; } printf ("%d\n", RotatingCalipers ()); } return 0; } |
- « 上一篇：poj1873