Pagini recente » Cod sursa (job #2849564) | Cod sursa (job #1366446) | Cod sursa (job #2045031) | Cod sursa (job #1900227) | Cod sursa (job #2665064)
//#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
pair<double,double> v[120005];
int hull[120005];
int cross_product(pair<int,int> P1,pair<int,int> P2,pair<int,int> P3){
return (P1.first-P2.first)*(P1.second-P3.second)-(P1.second-P2.second)*(P1.first-P3.first);
}
int aria(pair<int,int> a,pair<int,int> b,pair<int,int> c){
int a1=a.first,
a2=a.second,
b1=b.first,
b2=b.second,
c1=c.first,
c2=c.second;
return a1*b2+b2*c2+c1*a2-b2*c1-c2*a1-a2*b1;
}
bool ms(pair<int,int> a,pair<int,int> b){
return (cross_product(v[1],a,b)>=0);
}
int main(){
int mini=1,n;
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,ms);
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";
}
}