Pagini recente » Cod sursa (job #842853) | Cod sursa (job #3200963) | Cod sursa (job #1748810) | Cod sursa (job #1028180) | Cod sursa (job #2139301)
#include <bits/stdc++.h>
#define Point pair <double, double>
#define x first
#define y second
FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);
using namespace std;
/*--------Data--------*/
const int MAX = 12e4 + 2;
int n;
Point p[MAX];
int H[MAX], sz;
/*--------------------*/
void Read(){
scanf("%d", &n);
for(int i = 0; i < n; ++ i)
scanf("%lf%lf", &p[i].x, &p[i].y);
}
double Cross(const int &o, const int &a, const int &b){
Point O = p[o], A = p[a], B = p[b];
return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (A.y - O.y) * (B.x - O.x);
}
void Write(){
-- sz;
printf("%d\n", sz);
for(int i = 0; i < sz; ++ i)
printf("%.13f %.13f\n", p[H[i]].x, p[H[i]].y);
}
int main(){
Read();
sort(p, p + n);
for(int i = 0; i < n; ++ i){
while(sz >= 2 && Cross(H[sz - 2], H[sz - 1], i) <= 0)
-- sz;
H[sz++] = i;
}
for(int i = n - 2, t = sz + 1; i >= 0; -- i){
while(sz >= t && Cross(H[sz - 2], H[sz - 1], i) <= 0)
-- sz;
H[sz++] = i;
}
Write();
return 0;
}