Cod sursa(job #2500711)

Utilizator daniel96Daniel Dan daniel96 Data 28 noiembrie 2019 15:54:17
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <algorithm>
#include <deque>
#include <cmath>
#include <fstream>
using namespace std;
const long double PI=3.141592653589793238;
const int nm=120003;
typedef struct pct{long double x,y;};
pct a[nm];
deque <int> v;
bool ok, ut[nm];//ut[i]=true daca pct i a fost folosit
long double u,z,unghi;//pt tot felul de unghiuri
int i,n,in,po,c;//in=inceput, c=pct. curent
int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;
    in=1;
    for(i=1;i<=n;i++)fin>>a[i].x>>a[i].y;
    for(i=2;i<=n;i++)
        if((a[i].x<a[in].x)||((a[i].x==a[in].x)&&(a[i].y<a[in].y)))in=i;
    c=in;//punctul curent e cel de inceput
    u=0;
    do
    {
        v.push_back(c);//punem pe c in lista punctelor de pe infas. conv
        z=5000l;
        for(i=1;i<=n;i++)
            if((!ut[i])&&(i!=c))//daca nu am folosit inca punctul
        {
            unghi=atan2((a[i].x-a[c].x),(a[i].y-a[c].y));
            if(unghi<0)unghi+=2*PI;
            unghi-=u;
            if(unghi<0)unghi+=2*PI;
            if(z>unghi){z=unghi;po=i;}
        }
        u=atan2(-(a[c].x-a[po].x),-(a[c].y-a[po].y));
        if(u<0)u+=2*PI;
        c=po;//se actualizeaza pozitia
        ut[c]=true;
    }while(in!=c);//cat timp inceputul e diferit de nodul curent
    reverse(v.begin(),v.end());
    v.push_front(v.back());
    v.pop_back();
    fout<<v.size()<<"\n";
    for(i=0;i<v.size();i++)
        fout<<a[v[i]].x<<" "<<a[v[i]].y<<"\n";
    return 0;
}