Pagini recente » Cod sursa (job #728289) | Cod sursa (job #3123172) | Cod sursa (job #1914185) | Cod sursa (job #1357237) | Cod sursa (job #2539375)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,j,k;
pair <double,double> v[120001],s[120001];
double det(pair<double,double> a, pair<double,double> b, pair<double,double> c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(const pair<double,double> &a, const pair<double,double> &b){
double d=det(make_pair(0.0,0.0),a,b);
if(d!=0)
return d>0;
return a.x*a.x + a.y*a.y > b.x*b.x + b.y*b.y;
}
bool desc(const pair<double,double> &a, const pair<double,double> &b){
return a.x<b.x;
}
int main(){
fin>>n>>v[1].x>>v[1].y;
for(i=2;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[i].y<v[1].y)
swap(v[1],v[i]);
else
if(v[i].y==v[1].y && v[i].x<v[1].x)
swap(v[1],v[i]);
}
v[0]=v[1];
for(i=1;i<=n;i++){
v[i].x-=v[0].x;
v[i].y-=v[0].y;
}
sort(v+2,v+n+1,cmp);
for(i=3;i<=n;i++)
if(det(v[1],v[2],v[i])!=0)
break;
sort(v+2,v+i,desc);
s[1]=v[1];
s[2]=v[2];
k=2;
for(i=3;i<=n;i++){
while(k>2 && det(s[k-1],s[k],v[i])<0)
k--;
s[++k]=v[i];
}
fout<<k<<"\n";
for(i=1;i<=k;i++)
fout<<setprecision(6)<<fixed<<s[i].x+v[0].x<<" "<<s[i].y+v[0].y<<"\n";
return 0;
}