Pagini recente » Cod sursa (job #1409235) | Cod sursa (job #2848008) | Cod sursa (job #2109285) | Cod sursa (job #2403044) | Cod sursa (job #2660179)
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratore.in");
ofstream cout("infasuratoare.out");
pair<double,double> v[120005];
int cnt=2;
int st[120005];
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);
}
bool mysort(pair<double,double> a,pair<double,double> b){
if(a.first<=v[1].first and b.first>=v[1].first){
return false;
}
if(a.first>=v[1].first and b.first<=v[1].first){
return true;
}
if((a.first-v[1].first)*(b.second-v[1].second)==(b.first-v[1].first)*(a.second-v[1].second))
return dist2(a,v[1])>dist2(b,v[1]);
return (a.first-v[1].first)*(b.second-v[1].second)>(b.first-v[1].first)*(a.second-v[1].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);
}
bool verif(int c){
if(cnt==2)
return true;
int a=st[cnt-1];
int b=st[cnt];
if(calc_area(a,b,c)<=0)
return false;
return true;
}
int main()
{
int n,mini=0;
cin>>n;
v[0].second=1000000001;
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);
st[1]=1;
st[2]=2;
for(int i=3;i<=n;i++){
while(cnt>3 and verif(i)==false){
cnt--;
}
st[++cnt]=i;
}
cout<<cnt<<"\n";
for(int i=1;i<=cnt;i++){
cout<<v[st[i]].first<<" "<<v[st[i]].second<<"\n";
}
return 0;
}