Pagini recente » Cod sursa (job #185787) | Autentificare | Istoria paginii runda/din | Cod sursa (job #72617) | Cod sursa (job #2955985)
#include <iostream>
#include <fstream>
#include <iomanip>
#define MAXN 120000
#define MAXVAL 2000000000
using namespace std;
struct Point{
double x;
double y;
int id;
};
struct EdgeDegree{
double upper;
double lower;
bool minus = false;
Point end;
};
EdgeDegree v[MAXN], u[MAXN];
Point p[MAXN];
int compare(int a, int b){
if(a > b)
return 1;
if(a == b)
return 0;
return -1;
}
static inline int quickCompare(int a, int b){
if(v[a].minus && !v[b].minus)
return -1;
if(v[b].minus && !v[a].minus)
return 1;
return compare(v[a].upper * v[b].lower, v[a].lower * v[b].upper);
}
void quicksort(int begin, int end){
int b = begin, e = end, piv = (b + e) / 2;
EdgeDegree aux;
if(quickCompare(b, piv) == -1) // b < piv
b ++;
if(quickCompare(e, piv) == 1) // e > piv
e --;
while(b < e){
aux = v[b];
v[b] = v[e];
v[e] = aux;
do{
b ++;
} while(quickCompare(b, piv) == -1); // b < piv
do{
e --;
} while(quickCompare(e, piv) == 1); // e > piv
}
if(e > begin)
quicksort(begin, e);
if(e + 1 < end)
quicksort(e + 1, end);
}
/*
-1 = clockwise
0 = colineare
1 = ordine trigonometrica
*/
int getOrient(Point a, Point b, Point c){
int st = (a.y - b.y) * (b.x - c.x);
int dr = (b.y - c.y) * (a.x - b.x);
return compare(st, dr);
}
Point stv[MAXN];
int dr;
int main(){
int n, i, minp, j;
Point min;
ifstream fin ("infasuratoare.in");
fin >> n;
min = {MAXVAL, MAXVAL};
minp = 0;
for(i = 0; i < n; i ++){
fin >> p[i].x >> p[i].y;
p[i].id = i;
if(p[i].y < min.y || (p[i].y == min.y && p[i].x < min.x)){
min = p[i];
minp = i;
}
}
fin.close();
Point aux = p[0];
p[0] = p[minp];
p[minp] = aux;
// Punctul reper este acum p[0]
for(i = 1; i < n; i ++){
v[i - 1].upper = p[i].y - p[0].y;
if(v[i-1].upper < 0){
v[i-1].upper = -v[i-1].upper;
v[i-1].minus = !v[i-1].minus;
}
v[i - 1].lower = p[i].x - p[0].x;
if(v[i-1].lower < 0){
v[i-1].lower = -v[i-1].lower;
v[i-1].minus = !v[i-1].minus;
}
v[i - 1].end = p[i];
}
quicksort(0, n-2);
i = 0;
while(v[i].minus && i < n - 1){
u[n - 2 - i] = v[i];
i ++;
}
j = i;
while(j < n-1){
u[j - i] = v[j];
j ++;
}
// printf("\n");
// for(i = 0; i < n - 1; i ++){
// printf("%d: ", u[i].end.id);
// if(u[i].minus)
// printf("- ");
// printf("%.1f / %.1f\n", u[i].upper, u[i].lower);
// }
// printf("\n");
dr = 1;
stv[0] = p[0];
for(i = 0; i < n - 1; i ++){
while(dr > 1 && getOrient(stv[dr - 2], stv[dr - 1], u[i].end) != -1)
dr --;
stv[dr] = u[i].end;
dr ++;
}
ofstream fout ("infasuratoare.out");
fout << dr << endl;
fout << fixed;
fout << setprecision(6);
for(i = 0; i < dr; i ++)
fout << stv[i].x << " " << stv[i].y << endl;
fout.close();
return 0;
}