Pagini recente » Cod sursa (job #2912621) | Cod sursa (job #836283) | Cod sursa (job #18834) | Cod sursa (job #1297371) | Cod sursa (job #1721674)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double,double> pdd;
pdd V[120100],St[120100];
inline double cww(const pdd &a,const pdd &b,const pdd &c){return (b.x -a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);}
bool cmp(const pdd &a,const pdd &b){ return cww(V[1],a,b) < 0;}
int st,N,poz=1;
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> N;
for(int i = 1;i<=N;i++){
cin >> V[i].x >> V[i].y;
if(V[i] < V[poz]) poz = i;
}
swap(V[1],V[poz]);
sort(V+2,V+N+1,cmp);
St[1] = V[1];
St[2] = V[2];
st = 2;
for(int i = 3;i<=N;++i){
while(st >= 2 && cww(St[st-1],St[st],V[i]) > 0) --st;
St[++st] = V[i];
}
cout << st << fixed << setprecision(9) << '\n';
while(st>0) {cout << St[st].x << ' ' << St[st].y << '\n';--st;}
return 0;
}