Pagini recente » Cod sursa (job #50086) | Cod sursa (job #1062577) | Cod sursa (job #2909514) | Cod sursa (job #1537665) | Cod sursa (job #1970193)
//Convex Hull
//Jarvis' March
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct P
{
double x;
double y;
} V[10001];
int ConvexHull[10001];
int N,k=0;
int start;
int Used[10000];
void NormalizeAngle(double &angle)
{
if (angle<0) angle+=2* M_PI;
}
void run_ConvexHull()
{
int moved=1;
int current=start;
double last=0;
while(moved || start!= current)
{
moved = 0;
ConvexHull[++k]=current;
double maxAngle = 100000;
int next=current;
for(int i = 1; i <= N; ++i)
{
if (Used[i] || i == current) continue;
double angle= atan2((V[i].x - V[current].x),V[i].y- V[current].y);
NormalizeAngle(angle);
angle-=last;
NormalizeAngle(angle);
if (maxAngle>angle) maxAngle=angle,next=i;
}
last=atan2(-(V[current].x - V[next].x),-(V[current].y - V[next].y));
NormalizeAngle(last);
current=next;
Used[current] = 1;
}
}
int main()
{
f>>N;
for(int i=1; i<=N; i++)
{
double x,y;
f>>x>>y;
V[i]={x,y};
if(x<V[start].x) start=i;
}
V[0].x= 1000000000;V[0].y = 1000000000;
run_ConvexHull();
for(int i=k;i>=1;i--) g<<V[ConvexHull[i]].x<<' '<<V[ConvexHull[i]].y<<'\n';
}