Home Article Practice 凸包,模板

凸包,模板

2022-05-10 11:41  views:470  source:Coat    

#include<stdio.h>
#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) );
}



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)