Pagini recente » Cod sursa (job #592828) | Cod sursa (job #2195024) | Cod sursa (job #1748780) | Cod sursa (job #885804) | Cod sursa (job #2955844)
#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;
Point end;
};
EdgeDegree v[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){
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 = (begin + end) / 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, j, x, y, minp;
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] = p[0];
// Punctul reper este acum p[0]
for(i = 1; i < n; i ++){
v[i - 1].upper = p[i].y - p[0].y ;
v[i - 1].lower = p[i].x - p[0].x;
v[i - 1].end = p[i];
}
quicksort(0, n-2);
// for(i = 0; i < n - 1; i ++){
// printf("%d: %.1f / %.1f\n", v[i].end.id, v[i].upper, v[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], v[i].end) != -1)
dr --;
stv[dr] = v[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;
}