Pagini recente » Monitorul de evaluare | Cod sursa (job #59614) | Cod sursa (job #1761936) | Cod sursa (job #1034801) | Cod sursa (job #1343345)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 130010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,m;
int S[DIM];
pair<double,double> minim=make_pair(1000000000,1000000000);
pair<double,double> v[DIM];
int 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,k;
f>>n;
for(i=1;i<=n;i++){
f>>v[i].first>>v[i].second;
if(v[i].second<minim.second ||(v[i].second==minim.second && v[i].first<minim.first))
minim=v[i],p=i;
}
swap(v[1],v[p]);
sort(v+2,v+n+1,cmp);
S[1]=1,S[2]=2,k=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(12)<<fixed<<v[S[i]].first<<" "<<v[S[i]].second<<"\n";
f.close();
g.close();
return 0;
}