Pagini recente » Cod sursa (job #1715592) | Cod sursa (job #1804980) | Cod sursa (job #294272) | Cod sursa (job #829579) | Cod sursa (job #2526346)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int maxn = 120005;
struct xy {
double x, y;
bool operator < (xy other) {
if((*this).x == other.x) {
return (*this).y < other.y;
}
return (*this).x < other.x;
}
bool operator > (xy other) {
if((*this).x == other.x) {
return (*this).y > other.y;
}
return (*this).x > other.x;
}
};
xy v[maxn], mn;
xy st[maxn]; int k;
int n, i;
double determinant(xy a, xy b, xy c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(xy a, xy b) {
return determinant(v[1], a, b) < 0;
}
void sortpoints() {
int pos = 1;
mn = v[1];
for(i = 2; i <= n; i ++) {
if(v[i] < mn) {
mn = v[i]; pos = i;
}
}
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
}
void convexhull() {
st[1] = v[1];
st[2] = v[2];
k = 2;
for(i = 3; i <= n; i ++) {
while(k > 2 && determinant(st[k-1], st[k], v[i]) > 0) {
-- k;
}
st[++k] = v[i];
}
}
int main()
{
g << fixed << setprecision(9);
f >> n;
for(i = 1; i <= n; i ++) {
f >> v[i].x >> v[i].y;
}
sortpoints();
convexhull();
g << k << '\n';
for(i = k; i >= 1; i --) {
g << st[i].x << ' ' << st[i].y << '\n';
}
f.close(); g.close();
return 0;
}