Pagini recente » Cod sursa (job #1513944) | Cod sursa (job #1475881) | Cod sursa (job #1563150) | Cod sursa (job #203690) | Cod sursa (job #1550087)
#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];
double ccw(pn p1, pn p2, 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(pn p1, pn p2){
return (ccw(v[1],p1,p2)<0);
}
int N, head;
///////////////////////////////////////////////////////////////////////////
int main() {
pn mn;
mn.x=1000000005;
mn.y=1000000005;
int poz;
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;
}
}
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;
}