题意:输入一个凸包上的点(没有凸包内部的点,要么是凸包顶点,要么是凸包边上的点),判断这个凸包是否稳定。所谓稳
定就是判断能不能在原有凸包上加点,得到一个更大的凸包,并且这个凸包包含原有凸包上的所有点。
分析:容易知道,当一个凸包稳定时,凸包的每条边上都要有至少三个点,若只有两个点,则可以增加一个点,得到更大的凸
包。这样我们可以求出凸包,在求凸包时把共线的点也加进来,这样我们就判断是否有连续的三点共线即可,具体参见代码。
#include
#include
#include
#include
using namespace std;
const int N = 40005;
typedef double DIY;
struct Point
{
DIY x,y;
};
Point p[N];
Point stack[N];
Point MinA;
int top;
DIY dist(Point A,Point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
DIY cross(Point A,Point B,Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp(Point a,Point b)
{
DIY k=cross(MinA,a,b);
if(k>0) return 1;
if(k<0) return 0;
return dist(MinA,a)=1) --top;
stack[++top]=p[i];
}
}
bool Judge()
{
for(int i=1;i