Cod sursa(job #1153876)

Utilizator httpsLup Vasile https Data 25 martie 2014 20:03:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <conio.h>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

#define cout g

struct pct
{
    double x,y;
    int nr;
    bool operator !=(const pct &a) const
    {
        return !(x==a.x && y==a.y);
    }
} p[120010];
bool folosit[120010];
pct punct_curent( {1000000000,1000000000}),punct,punct_start;
int n,i,pluus(1);
double unghi,ug;
double dist(pct a,pct b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    f>>n;
    for(i=1; i<=n; ++i)
    {
        f>>p[i].x>>p[i].y;
        p[i].nr=i;
        if(p[i].y<punct_curent.y) punct_curent=p[i];
        else if(p[i].y==punct_curent.y && p[i].x<punct_curent.x) punct_curent=p[i];
    }
    punct_start=punct_curent;
    pluus=1;
    do
    {
        cout<<fixed<<setprecision(6)<<punct_curent.x<<' '<<punct_curent.y<<'\n';
        unghi=3*M_PI;
        for(i=1; i<=n; ++i)
            if(p[i]!=punct_curent)
            {
                ug=atan2(p[i].y-punct_curent.y,p[i].x-punct_curent.x);
                if(ug<0 && pluus) ug+=2*M_PI;
                if(ug<unghi) punct=p[i],unghi=ug;
                else if (ug==unghi) if(dist(p[i],punct_curent)>dist(punct,punct_curent)) punct=p[i],unghi=ug;
            }
        if(punct_curent.y>punct.y) pluus=0;
        punct_curent=punct;
        //getch();
    }
    while (punct_curent!=punct_start);
    return 0;
}