Cod sursa(job #1104556)

Utilizator s1mpMihai Alexandru s1mp Data 10 februarie 2014 21:02:25
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<iostream>
#include<fstream>
#include<iomanip>

#define Nmax 120001

using namespace std;

double X1[Nmax], Y1[Nmax];
int k;

void infasuratoare(int t, double X[Nmax], double Y[Nmax], int N) {
	int aux1 = t;
	int aux2 = (t + 1) % N;
	int aux3 = (t + 1) % N;
	while(aux3 != t) {
		for(int i = 0; i < N; i++) {
			if (i != aux1 && i != aux2) {
				double semn = X[aux2] * Y[i] + X[aux1] * Y[aux2] + X[i] * Y[aux1] - X[aux2] * Y[aux1] - X[i] * Y[aux2] - X[aux1] * Y[i];
				if (semn < 0) {
					aux2 = i;
				}
			}
		}
		aux1 = aux2;
		aux2 = (aux2 + 1) % N;
		aux3 = aux1;
		X1[k] = X[aux1];
		Y1[k++] = Y[aux1];
	}
}

int punctDeInceput(double X[Nmax], double Y[Nmax], int N) {
	int t = 0;
	for (int i = 1; i < N; i++) {
		if (X[t] > X[i]) {
			t = i;
		} else if (X[t] == X[i]) {
			if (Y[t] > Y[i]) {
				t = i;
			}
		}
	}
	return t;
}

int main() {
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	int N;
	double X[Nmax];
	double Y[Nmax];
	f >> N;
	for(int i = 0; i < N; i++) {
		f >> X[i];
		f >> Y[i];
	}
	int t = punctDeInceput(X,Y,N);
	infasuratoare(t,X,Y,N);
	g<<k<<endl;
	for(int i=0;i<k;i++) {
		g<<fixed<<setprecision(12)<<X1[i]<<" "<<setprecision(12)<<Y1[i]<<endl;
	}
	f.close();
	g.close();
	return 0;
}