Pagini recente » Cod sursa (job #845426) | Cod sursa (job #1155103) | Cod sursa (job #867152) | Cod sursa (job #1630499) | Cod sursa (job #943278)
Cod sursa(job #943278)
#include <fstream>
#include <algorithm>
#include <stack>
#include <cstdio>
using namespace std;
const int MAX_N = 120002;
typedef struct Point{
double x, y;
};
int N;
Point v[MAX_N], st[MAX_N];
inline double cross_product(Point a, Point b, Point c){
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
inline bool cmp(Point a, Point b){
return cross_product(v[1], a, b) < 0;
}
int main(){
ifstream f("infasuratoare.in");
freopen("infasuratoare.out", "w", stdout);
f >> N;
for(int i = 1; i <= N; ++i)
f >> v[i].x >> v[i].y;
int ind = 1;
for(int i = 2; i <= N; ++i)
if(v[i].x < v[ind].x)
ind = i;
else if(v[i].x == v[ind].x && v[i].y < v[ind].y)
ind = i;
Point tmp = v[1];
v[1] = v[ind], v[ind] = tmp;
sort(v+2, v+N+1, cmp);
st[1] = v[1], st[2] = v[2];
int top = 2;
for(int i = 3; i <= N; ++i){
while(top > 1 && cross_product(st[top-1], st[top], v[i]) > 0)
--top;
st[++top] = v[i];
}
printf("%d\n", top);
for(int i = top; i; --i)
printf("%.9lf %.9lf\n", st[i].x, st[i].y);
f.close();
return 0;
}