Cod sursa(job #2142416)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 24 februarie 2018 23:26:29
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
     double x,y;
}v[120001];




int compare (punct A,punct B)
{
    if(A.x==B.x)return(A.y<B.y);
    return (A.x<B.x);
}

 double poz1,last,poz2,maxim,minim,minim1,X,P1,P2;
 int n,i,t,P,POZ,Q,fv[120001],V[120001],ok,q;
int main()
{
    minim=INT_MAX;minim1=INT_MAX;

    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].x<minim){minim=v[i].x;minim1=v[i].y;POZ=i;}
        else if(v[i].x==minim){if(v[i].y<minim1){minim1=v[i].y;POZ=i;}}
    }





    ok=1;
    P=POZ;
    t=1;
    V[1]=P;
    while(ok)
    {

     minim=INT_MAX;maxim=INT_MIN;
     q=POZ;
    for(i=1;i<=n;i++)
     {
         if(i==POZ)continue;
         if(fv[i]==0)
         {

           X=atan2(v[i].x-v[POZ].x,v[i].y-v[POZ].y);
           if(X<0)X=X+2*M_PI;
           X=X-last;
           if(X<0)X=X+2*M_PI;
           if(X<minim){minim=X;q=i;}


         }
     }
     last=atan2(v[q].x-v[POZ].x,v[q].y-v[POZ].y);
    if(last<0)last=last+2*M_PI;


     POZ=q;fv[POZ]=1;
      if(P==POZ){ok=0;break;}
     t++;
     V[t]=POZ;





    }

     g<<t<<'\n';
     for(i=t;i>=1;i--)
     {
         g<<fixed<<setprecision(6)<<v[V[i]].x<<" ";
         g<<fixed<<setprecision(6)<<v[V[i]].y<<'\n';
     }
    return 0;
}