Pagini recente » Cod sursa (job #1097996) | Cod sursa (job #1866277) | Cod sursa (job #2771295) | Statistici Matei Ioan-Mihnea (Matei_Ioan_Mihnea_323CA) | Cod sursa (job #1469128)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 120000
#define INF 2000000000
#define EPS 0.00000000000001
double x[MAXN], y[MAXN];
int st[MAXN];
double mx = INF * 1.0, my = INF * 1.0;
inline double aria(int p1, int p2, int p3){
return (x[p2] - x[p1]) * (y[p3] - y[p1]) - (x[p3] - x[p1]) * (y[p2] - y[p1]);
}
inline double modul(double x){
return x < 0.0 ? -x : x;
}
inline char eq(double x, double y){
long long p = 1, nr = 0;
while(nr < 12 && modul(x) / 10 >= p * 1.0 || modul(y) / 10 >= p * 1.0){
p *= 10;
nr++;
}
if(x - y < -EPS * p)
return -1;
if(x - y > -EPS * p && x - y < EPS * p)
return 0;
return 1;
}
void qs(int st, int dr){
int i = st, j = dr, pv = st + rand() % (dr - st + 1);
double px = x[pv] - mx, py = y[pv] - my, aux;
while(i <= j){
while(eq((y[i] - my) * px, (x[i] - mx) * py) == -1)
i++;
while(eq((y[j] - my) * px, (x[j] - mx) * py) == 1)
j--;
if(i <= j){
aux = x[i]; x[i] = x[j]; x[j] = aux;
aux = y[i]; y[i] = y[j]; y[j] = aux;
i++; j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
int main(){
srand(time(NULL));
FILE *in = fopen("infasuratoare.in", "r");
int n, i, p;
double aux;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++){
fscanf(in, "%lf%lf", &x[i], &y[i]);
if(eq(mx, x[i]) == 1 || (eq(mx, x[i]) == 0 && eq(my, y[i]) == 1)){
mx = x[i];
my = y[i];
p = i;
}
}
aux = x[p]; x[p] = x[0]; x[0] = aux;
aux = y[p]; y[p] = y[0]; y[0] = aux;
fclose(in);
qs(1, n - 1);
int dr = 2;
st[0] = 0; st[1] = 1;
for(i = 2; i < n; i++){
while(eq(aria(st[dr - 2], st[dr - 1], i), 0) == -1)
dr--;
st[dr] = i;
dr++;
}
FILE *out = fopen("infasuratoare.out", "w");
fprintf(out, "%d\n", dr);
for(i = 0; i < dr; i++)
fprintf(out, "%lf %lf\n", x[st[i]], y[st[i]]);
fclose(in);
return 0;
}