Pagini recente » Cod sursa (job #2492021) | Cod sursa (job #996420) | Cod sursa (job #1148852) | Cod sursa (job #200641) | Cod sursa (job #861880)
Cod sursa(job #861880)
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define MAXN 120050
int N;
struct Point {
double x, y;
};
Point P[MAXN];
bool used[MAXN];
Point st[MAXN];
int head;
double crossProduct(const Point &A, const Point &B, const Point &C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(const Point &A, const Point &B) {
return crossProduct(P[0], A, B) > 0;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%lf %lf", &P[i].x, &P[i].y);
}
int first = 0;
for(int i = 0; i < N; i++)
if(P[i].y < P[first].y)
first = i;
swap(P[0], P[first]);
sort(P + 1, P + N, cmp);
st[0] = P[0];
st[1] = P[1];
head = 1;
for(int i = 2; i < N; i++) {
while(head >= 1 && crossProduct(st[head - 1], st[head], P[i]) < 0)
head--;
st[++head] = P[i];
}
printf("%d\n", head + 1);
for(int i = 0; i <= head; i++)
printf("%.6lf %.6lf\n", st[i].x, st[i].y);
return 0;
}