【GDKOI2006】防御力量题解

Description

Y国向X国发动了总进攻，X国在防御方面有着非常高的科技，他们在国内建了许多防御塔（共N个），两个防御塔间可以产生保护光膜（一种力场），通常情况下，X国的防御系统设定力场只在外围产生，即若把所有防御塔看成平面上N个点的点集，则力场只在点集的凸包（边上的也算在内）上相邻顶点之间产生。防御塔产生的保护膜异常坚实，而防御塔本身却相对比较脆弱，所以Y国打算集中火力破坏防御塔，可异由于火力不足每次只能攻陷一个防御塔。当一个防御塔被摧毁时，X国的防御系统马上自动调整，后果新计算
凸包，重新建立防御力场。Y国目标是摧毁A城，Y国可以摧毁一个城，条件是这个城在凸包上。

Input

第一行，一个整数N（3<=N<=10000）
接下来N行，每行表示一个防御塔的整数坐标（第一个数是横坐标，第二个数是纵坐标，绝对值<=10000）。
最后一行给出A城的整数坐标，含2个整数，表示横坐标和纵坐标(绝对值小于等于10000)。

Output

最少要摧毁的防防御塔数。

Sample Input

Sample Output

题目大意

已知一些点和一个特殊点 $A$ ，最外围形成了一个凸包，求最少删去多少个点可以使得 $A$ 成为凸包的一个顶点

题解

思考这样一件事情，那就是假如 $A$ 是凸包的一个顶点，那么这会有什么性质？

观察发现，一个凸包的所有内角都小于 $180^\circ$ ，也就是说，一定有一条直线 $AH$ 可以使得凸包在直线上或者一侧

那我们的目标转化为找直线

连接每个点与 $A$ 形成一条直线，易求它的函数解析式

可以很容易得判断出来，这些防御塔在直线的哪一侧（或者直线上）

那么我们只需要删除数量较少的一侧的点就可以了

枚举直线是 $O(n)$ 的，判断数量可以 $O(\log n)$ ，但是我使用的是 $O(n)$ 的暴力枚举

因为 $n \le 10^4$ ，所以常数小点 $O(n^2)$ 也是能过的，当然 $O(n \log n)$ 的算法是更优的

需要特判一下，当 $x_A = x_i$ 时，直线 $AI$ 是一条垂直于 $x$ 轴的直线， $k$ 值为无限大

其实判断左侧右侧可以根据横坐标的大小进行比较

然后没了

#include <cstdio>
using namespace std;
int n,ans=0x3f3f3f3f;
double x[10005],y[10005],ax,ay;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%lf%lf",x+i,y+i);
	scanf("%lf%lf",&ax,&ay);
	for (int i=1;i<=n;++i)
	{
		int up=0,down=0;
		if (ax==x[i]) {
			for (int j=1;j<=n;++j)
				if (x[j]>ax) ++down;
					else if (x[j]<ax) ++up;
		} else {
			double k=(ay-y[i])/(ax-x[i]);
			for (int j=1;j<=n;++j)
				if (y[j]<k*(x[j]-ax)+ay) ++down;
				else if (y[j]>k*(x[j]-ax)+ay) ++up;
		}if (up<ans) ans=up;if (down<ans) ans=down;
	}printf("%d\n",ans);
}