Cod sursa(job #417887)

Utilizator cretuMusina Rares cretu Data 14 martie 2010 23:44:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 120000;

struct Point{
	double x, y;
};

Point p[MAX];
int n;
int v[MAX];
int init = 0;

bool pointCmp (int a, int b) {
	return (p[a].x - p[init].x) * (p[b].y - p[init].y) < (p[a].y - p[init].y) * (p[b].x - p[init].x);
}

long double sign(Point p1, Point p2, Point p3 ) {
	return (long double)p1.x * p2.y + (long double)p2.x * p3.y + p3.x * p1.y - (long double)p1.y * p2.x - (long double)p2.y * p3.x - (long double)p3.y * p1.x;
}

void readPoints()
{
	ifstream fin("infasuratoare.in");
	fin >> n;

	int i;
	for (i = 0; i < n; ++i) {
		fin >> p[i].x >> p[i].y;
		if (p[i].x < p[init].x || (p[i].x == p[init].x && p[i].y < p[init].y)) init = i;
	}

	fin.close();
}

int main() {
	
	int i, j;
	init = 0;
	
	readPoints();

	for (i = 0, j = 0; i < n; ++i)
		if (i != init)
			v[j++] = i;

	sort(v, v+n-1, pointCmp);
	
	vector<int> st;
	st.push_back(init);

	for (i = 0; i < n-1; ++i) {
		while (st.size() > 1 && sign(p[st[st.size()-2]], p[st[st.size()-1]], p[v[i]]) > 0) 
			st.pop_back(); 
		st.push_back(v[i]);
	}

	reverse(st.begin(), st.end());
	FILE * fout = fopen("infasuratoare.out", "w");
	fprintf(fout, "%d\n",st.size());

	for (i = 0; i < st.size(); ++i) 
		fprintf(fout, "%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);
	fclose(fout);

	return 0;
}