Cod sursa(job #532055)

Utilizator ooctavTuchila Octavian ooctav Data 10 februarie 2011 19:29:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"infasuratoare.in"};
const char OUT[] = {"infasuratoare.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 120005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N;
PDD a[NMAX];
PDD p1, p2;
int jos[NMAX], sus[NMAX];
int ST[NMAX], ST2[NMAX];

bool comp(int x, int y)
{
	if(a[x].fs < a[y].fs)	return 1;
	if(a[x].fs == a[y].fs && a[x].ss < a[y].ss)	return 1;
	return 0;
}

bool comp2(int x, int y)
{
	if(a[x].fs > a[y].fs)	return 1;
	if(a[x].fs == a[y].fs && a[x].ss > a[y].ss)	return 1;
	return 0;
}

void citi()
{
	p1 = mp(INF, INF);
	p2 = mp(-INF, -INF);
	scanf("%d", &N);
	FOR(i, 1, N)
	{	
		scanf("%lf%lf", &a[i].fs, &a[i].ss);
		if(p1.fs > a[i].fs || (p1.fs == a[i].fs && p1.ss > a[i].ss))	p1 = a[i];
		if(p2.fs < a[i].fs || (p2.fs == a[i].fs && p2.ss < a[i].ss))	p2 = a[i];
	}
}

bool pozitiona(PDD a)
{
	double y = (p1.ss*(p1.fs - p2.fs) - (p1.fs - a.fs)*(p1.ss - p2.ss)) / (p1.fs - p2.fs);
	return a.ss < y;
}

void desparte()
{
	FOR(i, 1, N)
		if(a[i] == p1 || a[i] == p2)
			jos[++jos[0]] = i, sus[++sus[0]] = i;
		else if(pozitiona(a[i]))
			jos[++jos[0]] = i;
		else
			sus[++sus[0]] = i;
}

bool semn(int i1, int i2, int i3)
{
	return a[i1].fs*(a[i2].ss - a[i3].ss) + a[i2].fs*(a[i3].ss - a[i1].ss) + a[i3].fs*(a[i1].ss - a[i2].ss) > (double) 0;
}

void infasura()
{
	FOR(i, 1, jos[0])
	{
		while(ST[0] >= 2 && !semn(ST[ST[0] - 1], ST[ST[0]], jos[i]))	ST[0]--;
		ST[++ST[0]] = jos[i];
	}
	FOR(i, 1, sus[0])
	{
		while(ST2[0] >= 2 && !semn(ST2[ST2[0] - 1], ST2[ST2[0]], sus[i]))	ST2[0]--;
		ST2[++ST2[0]] = sus[i];
	}
}

void scrie()
{
	printf("%d\n", ST[0] + ST2[0] - 2);
	FOR(i, 1, ST[0])
		printf("%lf %lf\n", a[ST[i]].fs, a[ST[i]].ss);
	FOR(i, 2, ST2[0] - 1)
		printf("%lf %lf\n", a[ST2[i]].fs, a[ST2[i]].ss);
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	desparte();
	sort(jos + 1, jos + jos[0] + 1, comp);
	sort(sus + 1, sus + sus[0] + 1, comp2);
	//sortez jos si sus
	infasura();
	scrie();
	return 0;
}