Pagini recente » Cod sursa (job #734530) | Cod sursa (job #993150) | Cod sursa (job #2226714) | Cod sursa (job #2309683) | Cod sursa (job #1550091)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct pn{
double x,y;
}v[120010];
pn stk[120010];
int N, head;
double ccw(const pn& p1,const pn& p2,const pn& p3) // <0 dup acele cs // >0 impotriva acelor cs // =0 coliniare
{
return( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
}
bool cmp(const pn& p1,const pn& p2){
return (ccw(v[1],p1,p2)<0);
}
///////////////////////////////////////////////////////////////////////////
int main() {
pn mn;
mn.x=1000000005;
mn.y=1000000005;
cin >> N;
for(int i(1); i<=N; ++i){
cin >> v[i].x >> v[i].y;
/* if( (v[i].x<mn.x)&&(v[i].y<mn.y) ) {
mn.x=v[i].x;
mn.y=v[i].y;
poz=i;
} */
}
int poz=1;
for(int i(2); i<=N; ++i) if((v[i].x<v[poz].x)||(v[i].y<v[poz].y)) poz=i;
swap(v[1],v[poz]);
sort(v+2, v+N+1, cmp);
stk[1]=v[1]; stk[2]=v[2];
head=2;
for(int i=3; i<=N; ++i) {
while(head>=2 && ccw(stk[head-1],stk[head],v[i])>0) --head;
stk[++head]=v[i];
}
cout << head << "\n";
cout << fixed;
for(int i=head; i>=1; --i) cout << setprecision(9) << stk[i].x << " " << stk[i].y << "\n";
return 0;
}