Cod sursa(job #1970196)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 19 aprilie 2017 00:12:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
//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[120001];
int ConvexHull[120001];

int N,k=0;
int start;
int Used[120001];



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();
    g<<k<<'\n';
    for(int i=k;i>=1;i--) g<<V[ConvexHull[i]].x<<' '<<V[ConvexHull[i]].y<<'\n';
}