Pagini recente » Cod sursa (job #2082832) | Cod sursa (job #2258074) | Cod sursa (job #1480690) | Cod sursa (job #1243411) | Cod sursa (job #3280157)
#include <fstream>
#include <deque>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct pct{
long double x,y;
} v[120001];
deque<pct> q;
bool cmp(pct a,pct b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool det(pct a,pct b,pct c){
return (((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))<0);
}
int main()
{
int n,i;
cin>>n;
for(i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++){
///cout<<v[i].x<<" "<<v[i].y<<"\n";
while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])) q.pop_back();
q.push_back(v[i]);
}
for(i=n-1;i>=1;i--){
////cout<<v[i].x<<" "<<v[i].y<<"\n";
while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])) q.pop_back();
q.push_back(v[i]);
}
cout<<q.size()-1<<"\n";
for(i=0;i<q.size()-1;i++){
cout<<fixed<<setprecision(12)<<q[i].x<<" "<<q[i].y<<"\n";
}
return 0;
}