Pagini recente » Cod sursa (job #778636) | Cod sursa (job #1148430) | Cod sursa (job #2299930) | Cod sursa (job #2754742) | Cod sursa (job #1920842)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double,double> pdd;
pdd V[120100],St[120100];
double cww(pdd a,pdd b,pdd c){return (b.x -a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);}
bool cmp(pdd a,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;}
}