Cod sursa(job #1979114)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 9 mai 2017 18:15:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "infasuratoare"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 120010

double x[MAXN], y[MAXN];
int pts[MAXN], N;
int S[MAXN], sindex;

inline double cross(int i, int j) {
	return x[i] * y[j] - y[i] * x[j];
}

inline double cross(int i, int j, int k) {
	//printf("%d %d %d -- %.2lf\n", i, j, k, cross(i, j) + cross(j, k) + cross(k, i));
	return cross(i, j) + cross(j, k) + cross(k, i);
}

bool comp(int i, int j) {
	return cross(pts[0], i, j) < 0;
}

void buildC() {
	sindex = 0;
	for (int i = 0; i < N; ++i) {
		while (sindex >= 2 &&
			cross(S[sindex - 2], S[sindex - 1], pts[i]) > 0)
			--sindex;
		S[sindex++] = pts[i];
	}
}

void printC() {
	printf("%d\n", sindex);
	for (int i = sindex - 1; i >= 0; --i)
		printf("%lf %lf\n", x[S[i]], y[S[i]]);
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	scanf("%d", &N);
	int minIndex = 0;
	for (int i = 0; i < N; ++i) {
		pts[i] = i;
		scanf("%lf%lf", &x[i], &y[i]);
		if ((x[i] < x[minIndex]) ||
			(x[i] == x[minIndex] && y[i] < y[minIndex]))
			minIndex = i;
	}
	swap(pts[0], pts[minIndex]);
	sort(pts + 1, pts + N, comp);
	buildC();
	printC();
	return 0;
}