Pagini recente » Cod sursa (job #1927419) | Cod sursa (job #427514) | Cod sursa (job #2497792) | Cod sursa (job #228558) | Cod sursa (job #402612)
Cod sursa(job #402612)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define Nmax 120005
#define inf 1<<30
int n, i, j, niv, ;
int stiva[Nmax];
double xmin, ymin = inf, pctmin, A;
struct infasuratoare{
double x, y;
} V[Nmax];
int comp(infasuratoare a, infasuratoare b){
return a.x * b.y > b.x * a.y;
}
int convex (infasuratoare a, infasuratoare b, infasuratoare c){
A = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
if (A > 0)
return 1;
return 0;
}
int main (){
FILE * f = fopen ("infasuratoare.in", "r");
FILE * g = fopen ("infasuratoare.out", "w");
fscanf (f, "%d", &n);
for (i = 1 ; i <= n ; i++){
fscanf(f, "%lf %lf", &V[i].x, &V[i].y);
if (ymin > V[i].y){
xmin = V[i].x;
ymin = V[i].y;
pctmin = i;
}
}
for (i = 1 ; i <= n ; i++){
V[i].x -= xmin;
V[i].y -= ymin;
}
sort (V+2, V+n+1, comp);
stiva[1] = 1;
stiva[2] = 2;
niv = 2;
for (i = 3 ; i <= n ; i++){
while ( niv >= 3 && !convex(V[stiva[niv-1]], V[stiva[niv]], V[i]) )
niv --;
stiva[++niv] = i;
}
fprintf (g, "%d\n", niv);
for (i = 1 ; i <= niv ; i++)
fprintf (g, "%lf %lf\n", V[stiva[i]].x + xmin, V[stiva[i]].y + ymin);
fclose(f);
fclose(g);
return 0;
}