Pagini recente » Cod sursa (job #596797) | Cod sursa (job #1374801) | Cod sursa (job #2692907) | Cod sursa (job #1456456) | Cod sursa (job #2552747)
// Made in Sublime Text 3
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstdio>
using namespace std;
const int N = 12e4;
typedef double d;
typedef long double ld;
struct point{
d first, second;
bool operator < (const point a) const{
if(first == a.first) return second < a.second;
return first < a.first;
}
}p[5 + N];
point hull[5 + N];
int n;
bool Semn(point x, point y, point z){
return (x.first * y.second - x.second * y.first + y.first * z.second - y.second * z.first + z.first * x.second - z.second * x.first) >= 0;
}
void Compute_Hull(){
int vf1(0), vf2(0);
point A, B;
point up[5 + N], down[5 + N];
point st[5 + N];
A = p[1];
B = p[n];
st[++vf1] = p[1];
for(int i = 2; i <= n; i++){
while(vf1 > 1 && !Semn(st[vf1 - 1], st[vf1], p[i]))
vf1--;
st[++vf1] = p[i];
}
for(int i = 1; i <= vf1; i++)
hull[i] = st[i];
st[++vf2] = p[n];
for(int i = n - 1; i >= 1; i--){
while(vf2 > 1 && !Semn(st[vf2 - 1], st[vf2], p[i]))
vf2--;
st[++vf2] = p[i];
}
for(int i = 2; i <= vf2; i++)
hull[i + vf1 - 1] = st[i];
vf1 += vf2 - 2;
printf("%d\n", vf1);
for(int i = 1; i <= vf1; i++)
printf("%.12f %.12f\n", hull[i].first, hull[i].second);
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lf%lf", &p[i].first, &p[i].second);
}
sort(p + 1, p + n + 1);
Compute_Hull();
fclose(stdin);
fclose(stdout);
}