Pagini recente » Cod sursa (job #2927809) | Cod sursa (job #2365198) | Cod sursa (job #489487) | Cod sursa (job #131362) | Cod sursa (job #767051)
Cod sursa(job #767051)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define MaxVal 1000000005
using namespace std;
typedef struct {
double x, y;
} point;
vector<point> P;
point StartP;
int N;
// counter-clockwise if ccw > 0
// clockwise if ccw < 0
// ccw != 0 for this problem.
double ccw(point p1, point p2, point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
bool myComp(point p1, point p2) {
/*if (p1.x == StartP.x && p1.y == StartP.y) {
return true;
} else if (p2.x == StartP.x && p2.y == StartP.y) {
return false;
}
if (p1.x == StartP.x) {
return (p2.x < StartP.x);
} else if (p2.x == StartP.x) {
return (p1.x > StartP.x);
}
double tg1 = (p1.y - StartP.y) / (p1.x - StartP.x);
double tg2 = (p2.y - StartP.y) / (p2.x - StartP.x);
if ((tg1 > 0 && tg2 > 0) || (tg1 < 0 && tg2 < 0)) {
return (tg1 < tg2);
} else if (tg1 < 0) {
return false; // p2, p1
} else {
return true; // p1, p2
}*/
return (ccw(StartP, p1, p2) > 0);
}
void print_vec(int M) {
vector<point>::iterator it;
point St = *(P.begin());
printf("%d\n", M);
for (it = P.begin(); it != P.end(); it++) {
if ((*it).x == St.x && (*it).y == St.y && it != P.begin()) {
break;
}
printf("%lf %lf\n",(*it).x, (*it).y);
}
}
void sw(int poz1, int poz2) {
point aux;
aux = P[poz1];
P[poz1] = P[poz2];
P[poz2] = aux;
}
void Graham_Scan() {
int M = 1;
P.push_back(StartP);
for (int i = 2; i <= N; i++) {
while (ccw(P[M-1], P[M], P[i]) <= 0) {
if (M > 1) {
M--;
} else if (i == N){
break;
} else {
i++;
}
}
M++;
sw(i, M);
}
print_vec(M);
}
point new_point(double a, double b) {
point p;
p.x = a;
p.y = b;
return p;
}
void read_() {
scanf("%d", &N);
StartP.x = MaxVal;
StartP.y = MaxVal;
for (int i = 0; i < N; i++) {
double a, b;
scanf("%lf%lf", &a, &b);
point crt = new_point(a, b);
if (b < StartP.y || (b == StartP.y && a < StartP.x)) {
StartP = crt;
}
P.push_back(crt);
}
sort(P.begin(), P.end(), myComp);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read_();
Graham_Scan();
return 0;
}