Pagini recente » Borderou de evaluare (job #1757306) | Borderou de evaluare (job #545914) | Borderou de evaluare (job #2046377) | Borderou de evaluare (job #2225992) | Cod sursa (job #1988380)
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
FILE *in, *out;
int const nmax = 120000;
struct Point {
double x;
double y;
bool operator<(Point other) const {
if(x != other.x)
return (x < other.x);
else
return (y < other.y);
}
};
//|a.x a.y 1|
//|b.x b.y 1|
//|c.x c.y 1|
double det3(Point a, Point b, Point c) {
double plus = a.x * b.y + b.x * c.y + c.x * a.y;
double minus = b.y * c.x + c.y * a.x + a.y * b.x;
return (plus - minus);
}
int n;
Point v[1 + nmax];
Point sol[1 + nmax];
int nsol;
//pleci din a = v[1] in b si apoi in c si vezi ce intoarcere faci pe acest drum
bool cmp(Point b, Point c) {
return (det3(v[1], b, c) < 0);
}
int main() {
in = fopen("infasuratoare.in","r");
out = fopen("infasuratoare.out","w");
int n, imin = 1;
fscanf(in, "%d", &n);
for(int i = 1;i <= n;i ++) {
fscanf(in, "%lf %lf", &v[i].x, &v[i].y);
if(v[i] < v[imin])
imin = i;
}
swap(v[1], v[imin]); //punctul care e sigur pe infasuratoare il punem in v[1]
sort(v + 2, v + n + 1, cmp);
nsol = 2;
sol[1] = v[1];
sol[2] = v[2];
for(int i=3; i<=n; i++) {
while(2 < nsol && det3(sol[nsol-1], sol[nsol], v[i]) >= 0)
nsol--;
sol[++nsol] = v[i];
}
/*
for (int i = 3; i <= n; i++) {
while (2 < nsol && (det3(sol[nsol - 1], sol[nsol], v[i]) > 0))
nsol--;
nsol++;
sol[nsol] = v[i];
}
*/
fprintf(out, "%d\n", nsol);
for(int i = 1;i <= nsol;i ++){
fprintf(out, "%.6lf %.6lf\n", sol[i].x, sol[i].y);
}
return 0;
}