Cod sursa(job #830281)

Utilizator bratiefanutBratie Fanut bratiefanut Data 6 decembrie 2012 16:33:07
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#define nMax 120000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct{double x,y;};
Punct v[nMax],rez[nMax];
int n,i,k;
bool p(Punct p, Punct p1)
{return p.y<p1.y?true:p.y==p1.y?p.x<p1.x?true:false:false;}
int semn(Punct p,Punct p1,Punct p2)
{if((p1.x-p.x)*(p2.y-p.y)-(p2.x-p.x)*(p1.y-p.y)>0)
return 1;
else
return 0;}
int main()
{f>>n;
for(i=0;i<=n-1;i++)
f>>v[i].x>>v[i].y;
sort(v,v+n,p);
rez[1]=v[0];
k=1;
for(i=1;i<=n-1;i++)
{while(k > 1 && semn(rez[k-1], rez[k], v[i])!=1)
k--;
rez[++k]=v[i];}
for(i=n-2;i>=0;i--)
{while(k > 1 && semn(rez[k-1], rez[k], v[i])!=1)
k--;
rez[++k]=v[i];}
g<<k-1<<endl;
for(i=1;i<=k-1;i++)
g<<rez[i].x <<" "<<rez[i].y<<endl;
f.close();
g.close();
return 0;}