就是一个单纯的上凸壳

扫描法水过

#include
    
     using namespace std;const int N=600000;const double eps=1e-16;struct Point{	double x,y;	int id;	Point(double _x=0.0,double _y=0.0):x(_x),y(_y){}	friend Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}	friend Point operator - (Point A,Point B){return Point(A.x-B.x,A.y-B.y);}	friend Point operator * (Point A,double k){return Point(A.x*k,A.y*k);}	friend Point operator / (Point A,double k){return Point(A.x/k,A.y/k);}	friend bool  operator < (Point A,Point B){if(fabs(A.x-B.x)
     
      0)top--;//	top++;//	convex_hull[top]=p[now];//}void Push(int a){	while(top)	{		if(fabs(convex_hull[top].x-p[a].x)
      
       1&&Cross(p[a],convex_hull[top-1])<=Cross(convex_hull[top],convex_hull[top-1]))			top--;		else break;		}	convex_hull[++top]=p[a];}void Make_Convex_Hull(){	convex_hull[0]=convex_hull[top=1]=p[1];	for(int i=2;i<=n;i++){		Push(i);	}}bool cmp(Point A,Point B){	return A.id