Cod sursa(job #1802090)

Utilizator andreilucaLuca Andrei andreiluca Data 9 noiembrie 2016 20:59:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#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;
}