Pagini recente » Cod sursa (job #2253967) | Cod sursa (job #1222360) | Cod sursa (job #862306) | Cod sursa (job #1180738) | Cod sursa (job #2660656)
//#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
pair<double,double> v[100005];
int hull[100005];
double dist2(pair<double,double> a,pair<double,double> b){
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
double calc_area(int a,int b,int c){
double a1=v[a].first,
a2=v[a].second,
b1=v[b].first,
b2=v[b].second,
c1=v[c].first,
c2=v[c].second;
return (a1*b2+b1*c2+c1*a2-b2*c1-c2*a1-a2*b1);
}
double cross_product(pair<double,double>P1, pair<double,double> P2,pair<double,double> P3){
return (P2.first -P1.first)*(P3.second-P1.second)-(P2.second-P1.second)*(P3.first-P1.first);
}
bool mysort(pair<double,double> a,pair<double,double> b){
return cross_product(v[1],a,b)>=0;
}
int main()
{
int mini=0,n;
v[0].second=1000000002;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i].first>>v[i].second;
if(v[mini].second>v[i].second)
mini=i;
}
swap(v[1],v[mini]);
sort(v+2,v+n+1,mysort);
v[++n]=v[1];
hull[1]=1;
int cnt=1;
for(int i=1;i<=n;i++){
while(cnt>1 and cross_product(v[hull[cnt-1]],v[hull[cnt]],v[i])<=0){
cnt--;
}
hull[++cnt]=i;
}
cnt--;
cout<<cnt<<"\n";
for(int i=1;i<=cnt;i++){
cout<<fixed<<setprecision(6);
cout<<v[hull[i]].first<<" "<<v[hull[i]].second<<"\n";
}
return 0;
}
/*
a1 a2 1
b1 b2 1
c1 c2 1
a1 a2 1
b1 b2 1
*/