Pagini recente » Cod sursa (job #218943) | Cod sursa (job #1816079) | Cod sursa (job #2216718) | Cod sursa (job #2503969) | Cod sursa (job #3030624)
#include <stdio.h>
#include <algorithm>
#define DIM 150005
#define inf 1<<30
using namespace std;
int n, i, j, level, pointMin;
int Stack[ DIM ];
double xmin, ymin = inf, A;
struct Point{
double x,
y;
} Arr[DIM], aux;
int comp(Point a, Point b){
return a.x * b.y >= b.x * a.y;
}
int convex (Point a, Point b, Point 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", &Arr[i].x, &Arr[i].y);
if (ymin > Arr[i].y){
xmin = Arr[i].x;
ymin = Arr[i].y;
pointMin = i;
}
}
for (i = 1 ; i <= n ; i++){
Arr[i].x -= xmin;
Arr[i].y -= ymin;
}
aux = Arr[1];
Arr[1] = Arr[pointMin];
Arr[pointMin] = aux;
sort (Arr+2, Arr+n+1, comp);
Stack[1] = 1;
Stack[2] = 2;
level = 2;
for (i = 3 ; i <= n ; i++){
while ( level >= 3 && !convex(Arr[Stack[level-1]], Arr[Stack[level]], Arr[i]) )
level --;
Stack[++level] = i;
}
fprintf (g, "%d\n", level);
for (i = 1 ; i <= level ; i++)
fprintf (g, "%lf %lf\n", Arr[Stack[i]].x + xmin, Arr[Stack[i]].y + ymin);
fclose(f);
fclose(g);
return 0;
}