Pagini recente » Cod sursa (job #81216) | Cod sursa (job #233341) | Cod sursa (job #432494) | Cod sursa (job #1509550) | Cod sursa (job #1469115)
#include <stdio.h>
#define MAXN 120000
#define INF 2000000000
#define EPS 0.000000000001
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 abs(double x){
return x < 0.0 ? -x : x;
}
inline char eq(double x, double y){
long long p = 1;
while(abs(x) / 10 >= p * 1.0 || abs(y) / 10 >= p * 1.0)
p *= 10;
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 + dr) / 2;
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(){
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;
}