Pagini recente » Cod sursa (job #890672) | Cod sursa (job #2022316) | Cod sursa (job #506632) | Cod sursa (job #931161) | Cod sursa (job #2106689)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int s[120010],i,poz,h,n;
pair <double,double> v[120010],c;
int cmp (pair<double,double> a, pair <double,double> b){
if((a.y-c.y)*(b.x-c.x)-(a.x-c.x)*(b.y-c.y)<0)
return 1;
else
return 0;
}
double calc (pair<double,double> a, pair <double,double> b, pair <double,double> c){
return (b.x-c.x)*(a.y-c.y)-(b.y-c.y)*(a.x-c.x);
}
int main () {
fin>>n;
c.x=200000000;
c.y=200000000;
for(i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[i].x<c.x)
c=v[i],poz=i;
else
if(v[i].x==c.x && v[i].y<c.y)
c=v[i],poz=i;
}
v[poz]=v[1];
v[1]=c;
sort(v+2,v+n+1,cmp);
s[1]=1;
s[2]=2;
h=2;
for(i=3;i<=n;i++){
if(calc(v[s[h]],v[i],v[s[h-1]])<=0)
s[++h]=i;
else{
while(calc(v[s[h]],v[i],v[s[h-1]])>0)
h--;
s[++h]=i;
}
}
fout<<h<<"\n";
for(i=1;i<=h;i++)
fout<<setprecision(6)<<fixed<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}