Pagini recente » Cod sursa (job #2358535) | Cod sursa (job #2766356) | Cod sursa (job #3300585) | Cod sursa (job #1662901) | Cod sursa (job #863504)
Cod sursa(job #863504)
#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];
int st[MAXN];
int head;
bool v[MAXN];
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 A.y < B.y || (A.y == B.y && A.x < B.x);
if(A.x < B.x)
return true;
if(A.x > B.x)
return false;
return A.y < B.y;
}
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);
}
sort(P, P + N, cmp);
st[0] = 0;
st[1] = 1;
v[1] = true;
head = 1;
int dir = 1;
for(int i = 2; i >= 0; i += dir) {
if(i == N) {
dir = -dir;
continue;
}
if(v[i]) continue;
while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[i]) < 0) {
v[st[head]] = false;
head--;
}
v[i] = true;
st[++head] = i;
}
printf("%d\n", head);
for(int i = 0; i < head; i++)
printf("%.6lf %.6lf\n", P[st[i]].x, P[st[i]].y);
return 0;
}