Pagini recente » Cod sursa (job #2261508) | Cod sursa (job #2056643) | Cod sursa (job #2034509) | Istoria paginii runda/eusebiu_oji_2015_cls10 | Cod sursa (job #2953600)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define MAXN 120000
#define EPSILON 0.000000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x, y;
};
point p0;
point v[MAXN];
point ans[MAXN];
int ansSize;
bool comp(point a, point b) {
return (p0.y - a.y) * (p0.x - b.x) - (p0.y - b.y) * (p0.x - a.x) <= EPSILON;
}
bool isTrigonometricWay(point a, point b, point c) {
return (a.y - b.y) * (b.x - c.x) - (b.y - c.y) * (a.x - b.x) <= EPSILON;
}
int main() {
int n, i, posOfP0;
fin >> n;
posOfP0 = 0;
for ( i = 0; i < n; i++ ) {
fin >> v[i].x >> v[i].y;
if ( v[posOfP0].x > v[i].x )
posOfP0 = i;
}
p0.x = v[posOfP0].x;
p0.y = v[posOfP0].y;
v[posOfP0].x = v[n - 1].x;
v[posOfP0].y = v[n - 1].y;
sort(v, v + n - 1, comp);
ansSize = 3;
ans[0].x = p0.x;
ans[0].y = p0.y;
ans[1].x = v[0].x;
ans[1].y = v[0].y;
ans[2].x = v[1].x;
ans[2].y = v[1].y;
for ( i = 2; i < n - 1; i++ ) {
while ( !isTrigonometricWay(ans[ansSize - 2], ans[ansSize - 1], v[i]) )
ansSize--;
ans[ansSize].x = v[i].x;
ans[ansSize].y = v[i].y;
ansSize++;
}
fout << setprecision(15);
fout << ansSize << "\n";
for ( i = 0; i < ansSize; i++ ) {
fout << ans[i].x << " " << ans[i].y << "\n";
}
fin.close();
fout.close();
return 0;
}