Pagini recente » Cod sursa (job #658742) | Cod sursa (job #1027285) | Istoria paginii runda/oji_09_2012/clasament | Cod sursa (job #2079699) | Cod sursa (job #1545863)
#include <cstdio>
#include <algorithm>
#define MAXN 120000
#define INF 2000000000000000.0
#define EPS 0.0000000001
typedef struct{
double x, y;
}punct;
int sv[MAXN];
punct v[MAXN];
inline char eq(double a, double b){
if(a - b > EPS)
return 1;
if(a - b < -EPS)
return -1;
return 0;
}
inline double aria(punct a, punct b, punct c){
return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}
inline int cmp(punct x, punct y){
return aria(v[0], x, y) > 0;
}
void qs(int st, int dr){
int i = st, j = dr;
punct piv = v[(st + dr) / 2], aux;
while(i <= j){
while(cmp(piv, v[i]) == 1)
i++;
while(cmp(v[j], piv) == 1)
j--;
if(i <= j){
aux = v[i]; v[i] = v[j]; v[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;
punct m;
m.x = INF; m.y = INF;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++){
fscanf(in, "%lf%lf", &v[i].x, &v[i].y);
if(eq(m.x, v[i].x) == 1){
m = v[i];
p = i;
}
else if(eq(m.x, v[i].x) == 0 && eq(m.y, v[i].y) == 1){
m = v[i];
p = i;
}
}
fclose(in);
punct aux;
aux = v[p]; v[p] = v[0]; v[0] = aux;
std::sort(v + 1, v + n, cmp);
sv[0] = 0;
sv[1] = 1;
int dr = 2;
for(i = 2; i < n; i++){
while(dr > 2 && eq(aria(v[sv[dr - 2]], v[sv[dr - 1]], v[i]), 0) == -1)
dr--;
sv[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", v[sv[i]].x, v[sv[i]].y);
fclose(out);
return 0;
}