Cod sursa(job #1922719)

Utilizator Julian.FMI Caluian Iulian Julian. Data 10 martie 2017 18:36:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <vector>
//#include <iostream>
#include <iomanip>
#include <limits>
#define nmax 120009
using namespace std;
int xmin,ymin;
struct punct{
double x,y,tg;
}p[nmax];

vector<int> S;

bool cmp(punct a,punct b){
    return a.tg<b.tg;
}

bool arie(double x1,double y1,double x2,double y2,double x3,double y3){
    double arie=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
    return arie>=0;
}

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int main(){
int n,i;
fin>>n;
int org=1;
for(i=1;i<=n;i++)
{
    fin>>p[i].x>>p[i].y;
    if(p[org].x > p[i].x || (p[org].x==p[i].x && p[org].y>p[i].y))org=i;
}

xmin=p[org].x;
ymin=p[org].y;
swap(p[1],p[org]);
p[1].x=0;p[1].y=0;
p[n+1]=p[1];

for(i=2;i<=n;i++)
{
    p[i].x-=xmin;
    p[i].y-=ymin;
    if(p[i].x==0)p[i].tg=numeric_limits<double>::max();
    else p[i].tg=p[i].y/p[i].x;
}


sort(p+2,p+n+1,cmp);

int p1,p2,p3;
S.push_back(0);
S.push_back(1);
for(i=2;i<=n+1;i++)
{ p1=i;
  p2=S[S.size()-1];S.pop_back();
  p3=S[S.size()-1];
    while(S.size()>1 && !arie(p[p3].x,p[p3].y,p[p2].x,p[p2].y,p[p1].x,p[p1].y))
    {p2=S[S.size()-1];S.pop_back();
     p3=S[S.size()-1];
    }
S.push_back(p2);
S.push_back(p1);
}

fout<<S.size()-2<<'\n';
for(i=2; i<S.size(); i++)fout<<setprecision(8)<<fixed<<(p[S[i]].x+xmin)<<' '<<p[S[i]].y+ymin<<'\n';
}