Pagini recente » Cod sursa (job #2631956) | Cod sursa (job #1775765) | Clasament moisil2017-1112 | Cod sursa (job #1173868) | Cod sursa (job #2957583)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#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;
}
bool sortCompare(EdgeDegree a, EdgeDegree b){
double left = a.upper * b.lower;
double right = a.lower * b.upper;
if(a.minus && !b.minus)
return true;
if(!a.minus && b.minus)
return false;
if(a.minus && b.minus)
return left > right;
return left < right;
}
/*
-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;
// printf("%f %f\n", p[0].x, p[0].y);
// 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].end = p[i];
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 = true;
}
}
// quicksort(0, n-2);
sort(v, v + n-1, sortCompare);
i = 0;
while(v[i].minus && i < n-1)
i ++;
j = 0;
while(i < n - 1){
u[j] = v[i];
i ++;
j ++;
}
i = 0;
while(j < n - 1){
u[j] = v[i];
i ++;
j ++;
}
// printf("\n");
// for(i = 0; i < n - 1; i ++){
// printf("%d: ", v[i].end.id);
// if(v[i].minus)
// printf("- ");
// printf("%.1f / %.1f\n", v[i].upper, v[i].lower);
// }
// printf("\n");
// 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;
}