Cod sursa(job #2245742)

Utilizator PhilipDumitruPhilip Dumitru PhilipDumitru Data 25 septembrie 2018 19:31:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
// InfasuratoareConvexa.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <cstdlib>

#define EPS 0.000000000001

struct Point {
	double x;
	double y;
};

int n;
Point pct[120000];

int st[120000];
int head;

double crossProduct(Point*A, Point*B, Point*C) {
	double res = (B->x - A->x)*(C->y - A->y) - (B->y - A->y)*(C->x - A->x);
	return res;
}

int comparePoints(const void * a, const void * b) {
	double prod = crossProduct(pct, (Point*)a, (Point*)b);

	if (prod > 0) return -1;
	return 1;
}

int main() {
	FILE * fin;
	FILE * fout;
	int A;

	fin = fopen("infasuratoare.in", "r");
	fout = fopen("infasuratoare.out", "w");

	fscanf(fin, "%d", &n);
	fscanf(fin, "%lf%lf", &pct[0].x, &pct[0].y);
	A = 0;
	for (int i = 1; i < n; ++i) {
		fscanf(fin, "%lf%lf", &pct[i].x, &pct[i].y);
		if (pct[i].x < pct[A].x) {
			A = i;
		} else if ((pct[i].x == pct[A].x) && (pct[i].y < pct[A].y)) {
			A = i;
		}
	}
	if (A) {
		double x, y;
		x = pct[A].x;
		pct[A].x = pct[0].x;
		pct[0].x = x;
		y = pct[A].y;
		pct[A].y = pct[0].y;
		pct[0].y = y;
	}
	qsort(pct + 1, n - 1, sizeof(Point), comparePoints);

	head = -1;
	st[++head] = 0;
	st[++head] = 1;
	for (int i = 2; i < n; ++i) {
		while (head >= 2 && crossProduct(pct + st[head], pct + st[head-1], pct + i) > EPS) {
			--head;
		}
		st[++head] = i;
	}

	fprintf(fout, "%d\n", head+1);
	for (int i = 0; i <= head; i++)
	{
		fprintf(fout, "%f %f\n", pct[st[i]].x, pct[st[i]].y);
	}

	fclose(fin);
	fclose(fout);
    return 0;
}