凸包,模板
#include<algorithm>
#include<math.h>
using namespace std;
const int INF = 50005;
struct node
{
double x,y;
};
node data[INF];
node res[INF];
double Graham(node* data,node* res, int n);
double cross(node a, node b, node mark);
double dis(node a, node b);
long long dis1(node a, node b);
bool cmp(node a,node b)
{
double ans = cross(a,b,data[0]);
if(ans > 0 || (ans == 0 && dis(a,data[0]) < dis(b,data[0]))) return true;
return false;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lf %lf",&data[i].x,&data[i].y);
int len = Graham(data,res,n);
long long max = -1;
for(int i = 0; i <len; i++)
{
printf("%lf %lf\n",res[i].x,res[i].y) ;
}
return 0;
}
double Graham(node* data,node* res, int n)
{
int t = 0;
for(int i = 1; i <n; i++)
{
if(data[t].y > data[i].y || (data[t].y == data[i].y) && data[t].x > data[i].x)
t = i;
}
node temp = data[t];
data[t] = data[0];
data[0] = temp;
/*
for(int i = 1; i < n; i++)
{
int t = i;
for(int j =i+1; j < n; j++)
{
double flag = cross(data[t],data[j],data[0]);
if(flag < 0 || ( flag == 0 && dis(data[t],data[0]) > dis(data[j], data[0]) ) )
t = j;
}
node temp1 = data[t];
data[t] = data[i];
data[i] = temp1;
}
*/
sort(data + 1,data + n,cmp);
res[0] = data[0];
int top = 0;
for(int i = 1; i < n; i++)
{
while(top > 0 && cross(res[top-1], data[i] ,res[top]) >= 0)
top--;
res[++top] = data[i];
}
return top + 1;
}
double cross(node a, node b, node mark)
{
return (a.x - mark.x) * (b.y - mark.y) - (b.x - mark.x) * (a.y - mark.y);
}
double dis(node a, node b)
{
return sqrt( (a.x -b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}