Pagini recente » Cod sursa (job #106946) | Autentificare | Cod sursa (job #2348545) | Cod sursa (job #2303591) | Cod sursa (job #1343348)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 130010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
int S[DIM];
pair<double,double> v[DIM],aux;
double det(const pair<double,double> &a,const pair<double,double> &b,const pair<double,double> &c){
return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
int cmp(const pair<double,double> &a,const pair<double,double> &b){
return (det(v[1],a,b)>0);
}
int main(void){
register int i,j,p,q,k;
register double x,y;
f>>n;
p=1;
for(i=1;i<=n;i++){
f>>x>>y,v[i]=make_pair(x,y);
if(v[p]>v[i]) p=i;
}
swap(v[1],v[p]);
sort(v+2,v+n+1,cmp);
S[1]=1,k=2,S[2]=2;
for(i=3;i<=n;i++){
while(k>1 && det(v[S[k-1]],v[S[k]],v[i])<=0)
k--;
S[++k]=i;
}
g<<k<<"\n";
for(i=1;i<=k;i++){
g<<setprecision(9)<<fixed<<v[S[i]].first<<" "<<v[S[i]].second<<"\n";
}
return 0;
}