?? pku2187.cpp
字號:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
int x, y;
double ang;
} Point;
Point p[50010];
int cmp(const void *a, const void *b)
{
Point *c = (Point *)a;
Point *d = (Point *)b;
if (fabs(c->ang - d->ang) < 1e-6)
{
return abs(c->x - p[0].x) - abs(d->x - p[0].x) + abs(c->y - p[0].y) - abs(d->y - p[0].y);
}
else if (c->ang > d->ang)
{
return 1;
}
else
{
return -1;
}
}
int cross(int a, int b, int c)
{
return (p[b].x - p[a].x) * (p[c].y - p[b].y) - (p[b].y - p[a].y) * (p[c].x - p[b].x);
}
int main()
{
int i, j;
int n, tmp, left;
int stack[500010], top;
int C;
while (scanf("%d", &n) != -1 && n != 0)
{
for (i = 0; i < n; i++)
{
scanf("%d %d", &p[i].x, &p[i].y);
}
if (n == 1)
{
printf("0\n");
continue;
}
if (n == 2)
{
C = (p[0].x - p[1].x) * (p[0].x - p[1].x)+ (p[0].y - p[1].y) * (p[0].y - p[1].y);
printf("%d\n", C);
continue;
}
for (i = 1, left = 0; i < n; i++)
{
if (p[i].x < p[left].x)
{
left = i;
}
else if (p[i].x == p[left].x && p[i].y < p[left].y)
{
left = i;
}
}
tmp = p[0].x;
p[0].x = p[left].x;
p[left].x = tmp;
tmp = p[0].y;
p[0].y = p[left].y;
p[left].y = tmp;
for (i = 1; i < n; i++)
{
p[i].ang = atan2(p[i].y - p[0].y, p[i].x - p[0].x);
}
qsort(p+1, n - 1, sizeof(p[0]), cmp);
stack[0] = 0;
for (i = 1; i < n; i++)
{
if (fabs(p[1].ang - p[i].ang) > 1e-6)
{
stack[1] = i - 1;
break;
}
}
top = 1;
for (i = 2; i < n; i++)
{
if (i < n - 1 && fabs(p[i].ang - p[i+1].ang) < 1e-6)
{
continue;
}
while (cross(stack[top-1], stack[top], i) < 0)
{
top--;
}
top++;
stack[top] = i;
}
top++;
for (i = 0, C = 0; i < top - 1; i++)
{
for (j = i + 1; j < top; j++)
{
tmp = (p[stack[i]].x - p[stack[j]].x) * (p[stack[i]].x - p[stack[j]].x)
+ (p[stack[i]].y - p[stack[j]].y) * (p[stack[i]].y - p[stack[j]].y);
if (tmp > C)
{
C = tmp;
}
}
}
printf("%d\n", C);
}
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -