文章目录
  1. 1. E - Beauty Contest POJ - 2187
    1. 1.1. 题意
    2. 1.2. 思路
    3. 1.3. 凸包
      1. 1.3.1. 凸包是个啥卵东西?
      2. 1.3.2. 咋算??????
      3. 1.3.3. 标号思路补充
    4. 1.4. AC代码

引言:emm…怎么说呢…白书确实很烂…


E - Beauty Contest POJ - 2187

题意

题意很简单,就是找最远的两个点,输出他们间距离的平方,O(n2)O(n^2)是会TLE的。

思路

既然暴力会TLE,可以想到其实有很多点都不需要考虑。

经过一番思考后查书可以知道这个其实就是一个凸包问题,求出凸包,对凸包上的点进行暴力求解就好了,当然如果采取更NB的做法也行。

凸包

凸包是个啥卵东西?

好吧原谅我说了这么多还是没说凸包怎么算。

瞅瞅 百度百科 看右边张图就好了。我们用一个圈去裹住中间的一群点,裹紧了之后的圈就是凸包。

咋算??????

别急……我们使用Graham扫描算法。

这个扫描算法是要一个一个围成一个凸包,那么我们先确定凸包上的一个点作为极点。

选谁好呢?开心一点选横坐标最小的那个就好了。反证法,假设横坐标最小的点之一为A,A不在凸包上,那么必定凸包要将其包裹在内,那么凸包内某点横坐标必定小于A,与假设推出矛盾。

找到一个凸包上的点,我们称它为极点,我们建立极坐标。

极点

怎么标号好呢?我们以逆时针方向为其他点标号,极点的“大摆锤”无限长,先扫到谁谁就是1号,假如有多个点与极点同处一条直线,则按照距离从小到大标号(标号方法和下面说的向量叉乘法一致)。于是:

标号

然后怎搞???

别急,先瞅瞅目标图想想思路……

目标图

假设所有线段都是有方向的,比如 01\vec{01}13\vec{13}36\vec{36}。我们发现凸包内的点都在边的左侧,bingo~

还记得右手螺旋定律和叉乘吗?我们可以用这种方法判断一条线段在另一条线段左侧还是右侧。

假设 12\vec{12}13\vec{13},我们用右手螺旋定律发现13×12\vec{13}\times\vec{12}的向量向上,为正。同理,我们发现对所有的向量边和凸包内的点都适用。

哎呀,那就好搞了。

我们先把01\vec{01}12\vec{12}入栈,假设它们是凸包上的点。实际上我们的操作是将点0,点1和点2推入vector,默认存在方向。

入栈

现在它是这样的了。是时候考虑点3了,我们将点3也搭进来,发现它一点也不凸,明显是个异类,表现在向量上 就是13\vec{13}12\vec{12}的右边,那怎么行,我们可是观察出来了后来的边是要在前面的边的左边的。

于是我们让13×12\vec{13}\times\vec{12}发现大于0,于是挖掉叛徒2,vector里面还剩了0,1,发现03×01\vec{03}\times\vec{01}是小于0的,嗯,对的,把3加入vector。

现在vector里面是0,1,3。

同理考虑加入4,发现14×13\vec{14}\times\vec{13}是小于0的,这意味着4加入之前不用删3。点4加入,现在vector里面是0,1,3,4。

同理考虑加入5,发现35×34\vec{35}\times\vec{34}是大于0的,加入5之前需要删4。现在vector里面是0,1,3。发现15×13\vec{15}\times\vec{13}是大于0的,不需要删3。点5加入。现在vector里面是0,1,3,5。

同理考虑加入6,删点5,加点6。

……

目标图

好吧,最后完美了。

标号思路补充

确定极点O后,为点标号可以使用std::sort,在cmp函数中用叉乘的方法挨个计算OA×OB\vec{OA}\times\vec{OB} 的正负,如果是正说明A在B的外侧(如上图点1在点2的外侧),如果等于0说明两点与极点处在同一条直线上,按照距离确定顺序。

AC代码

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
#define _CRT_SECURE_NO_WARNINGS
#pragma comment (linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<ct0e>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
#define MOD (ll)(1e9+7)
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
struct coo
{
int x,y;
}co[50010];
int index;
vector<coo> vec;
int check(coo a,coo b,coo c)
{
int x1=a.x-c.x;
int y1=a.y-c.y;
int x2=b.x-c.x;
int y2=b.y-c.y;
return x1*y2-x2*y1;
}
bool cmp(coo a,coo b)
{
coo c=co[0];
int k=check(a,b,c);
if(!k)
{
int x1=a.x-c.x;
int y1=a.y-c.y;
int x2=b.x-c.x;
int y2=b.y-c.y;
return x1*x1+y1*y1<x2*x2+y2*y2;
}
else return k>0;
}
int main(void)
{
//freopen("in.txt","r",stdin);
//freopen("mine.txt","w",stdout);
int N;
while(scanf("%d",&N)==1)
{
int xmin=INF;
for(int i=0;i<N;i++)
{
co[i].x=read();
co[i].y=read();
if(co[i].x<xmin)
{
xmin=co[i].x;
index=i;
}
}
swap(co[0],co[index]);//关键步骤,我因为这步调试了很久
sort(co+1,co+N,cmp);
vec.clear();
vec.push_back(co[0]);
vec.push_back(co[1]);
int cnt=1;
for(int i=2;i<N;)
{
if(cnt-1>=0 && check(co[i],vec[cnt],vec[cnt-1])>0)
{
vec.pop_back();
cnt--;
}
else
{
vec.push_back(co[i]);
cnt++;
i++;
}
}
int maxn=-INF;
for(int i=0;i<vec.size();i++)
{
for(int j=i+1;j<vec.size();j++)
{
maxn=max(maxn,(vec[i].x-vec[j].x)*(vec[i].x-vec[j].x)+(vec[i].y-vec[j].y)*(vec[i].y-vec[j].y));
}
}
printf("%d\n",maxn);
}
return 0;
}
文章目录
  1. 1. E - Beauty Contest POJ - 2187
    1. 1.1. 题意
    2. 1.2. 思路
    3. 1.3. 凸包
      1. 1.3.1. 凸包是个啥卵东西?
      2. 1.3.2. 咋算??????
      3. 1.3.3. 标号思路补充
    4. 1.4. AC代码