|
|
題目大意：
給一堆點，求直線距離最遠的兩個點。
思路：
就是求“凸多邊形的直徑”。google一下，很多結果的啦。
首先要求出凸包，然后用一個比較牛逼的算法貌似可以在O(N)時間內求出凸包直徑。
但是那算法太復雜啦，看了半天都看不懂，所以就枚舉凸包每兩個點之間的距離了。
還是能200+ms過，因為凸包求出來以后，N就大大減小了。
 #include <stdio.h>
#include <stdlib.h>
  struct point  {
 short x, y;
 };
struct point points[50024], *convex[50024];
int points_cnt, convex_cnt;
__inline void swap(struct point *a, struct point *b)
{
struct point t = *a;
*a = *b;
*b = t;
}
__inline int cmp(struct point *p1, struct point *p2)
{
int a, b, c, d, r;
a = p1->y - points[0].y;
b = p1->x - points[0].x;
c = p2->y - points[0].y;
d = p2->x - points[0].x;
r = a*d - b*c;
  if (!r) {
if (b)
return b - d;
return a - c;
 }
return r;
}
__inline int turn_left(struct point *p1, struct point *p2, struct point *p3)
{
return (int)p1->x*p2->y - (int)p1->x*p3->y - (int)p2->x*p1->y +
(int)p3->x*p1->y + (int)p2->x*p3->y - (int)p3->x*p2->y
>= 0;
}
void qs(struct point *arr, int len)
{
int l, r, p;
if (len < 2)
return ;
l = 0;
p = len - 1;
r = len - 2;
while (1) {
while (l < p && cmp(&arr[l], &arr[p]) < 0)
l++;
while (r >= 0 && cmp(&arr[r], &arr[p]) >= 0)
r--;
if (l > r)
break;
swap(&arr[l], &arr[r]);
}
swap(&arr[l], &arr[p]);
qs(arr, l);
qs(arr + l + 1, len - l - 1);
}
int main()
{
int i, j, x, y, left, down, min_idx, max_val, val;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &points_cnt);
left = down = 0x7fffffff;
for (i = 0; i < points_cnt; i++) {
scanf("%d%d", &x, &y);
points[i].x = x;
points[i].y = y;
if (x < left || (x == left) && y < down) {
left = x;
down = y;
min_idx = i;
}
}
swap(&points[0], &points[min_idx]);
qs(points + 1, points_cnt - 1);
convex_cnt = 0;
convex[convex_cnt++] = &points[0];
convex[convex_cnt++] = &points[1];
for (i = 2; i < points_cnt; i++) {
while (convex_cnt >= 2 &&
!turn_left(convex[convex_cnt - 2],
convex[convex_cnt - 1],
&points[i]))
{
convex_cnt--;
}
convex[convex_cnt++] = &points[i];
}
max_val = 0;
for (i = 0; i < convex_cnt - 1; i++) {
for (j = i + 1; j < convex_cnt; j++) {
x = convex[i]->x - convex[j]->x;
y = convex[i]->y - convex[j]->y;
val = x*x + y*y;
if (val > max_val)
max_val = val;
}
}
printf("%d\n", max_val);
return 0;
}
|