Pagini recente » Cod sursa (job #2231824) | Cod sursa (job #658365) | Cod sursa (job #1770417) | Cod sursa (job #730387) | Cod sursa (job #1802090)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
using namespace std;
FILE *in = freopen("infasuratoare.in", "r", stdin);
FILE *out = freopen("infasuratoare.out", "w", stdout);
int n;
struct punct {
double x, y;
};
vector<punct> v;
vector<punct> convexHull(vector<punct> points);
double computeArea(punct a, punct b, punct c);
int main() {
scanf("%d", &n);
punct q;
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &q.x, &q.y);
v.push_back(q);
}
vector<punct> hull = convexHull(v);
for (int i = 0; i < hull.size(); i++) {
printf("%lf %lf\n", hull[i].x, hull[i].y);
}
return 0;
}
vector<punct> convexHull(vector<punct> points) {
int i, j, k;
vector<punct> hull;
punct left = points[0];
for (i = 1; i < points.size(); i++) {
if (points[i].x < left.x) {
left = points[i];
}
}
int sign = 1;
hull.push_back(left);
for (i = 0; i < points.size(); i++) {
for (j = 0; j < points.size(); j++) {
if (i != j) {
sign = 0;
for (k = 0; k < points.size(); k++) {
if (i != k) {
if (points[i].x == points[j].x && points[i].x == points[k].x || points[i].y == points[j].y && points[i].y == points[k].y) {
break;
}
if (sign == -1 && computeArea(points[i], points[j], points[k]) > 0) {
break;
}
if (sign == 1 && computeArea(points[i], points[j], points[k]) < 0) {
break;
}
if (computeArea(points[i], points[j], points[k]) < 0) {
sign = -1;
}
if (computeArea(points[i], points[j], points[k]) > 0) {
sign = 1;
}
}
}
if (k == points.size()) {
int count;
for (count = 0; count < hull.size(); count++) {
if (points[j].x == hull[count].x && points[j].y == hull[count].y) {
break;
}
}
if (count == hull.size()) {
hull.push_back(points[j]);
}
}
}
}
}
return hull;
}
double computeArea(punct a, punct b, punct c) {
return a.x*b.y + b.x*c.y + a.y*c.x - c.x * b.y - a.y * b.x - c.y *a.x;
}