Cod sursa(job #2351032)

Utilizator mihaigrozaGroza Mihai mihaigroza Data 21 februarie 2019 21:38:45
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>

using namespace std;

vector<int> v;
double x[120000],y[120000];
int n,verif[120000];

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int main()
{
    f>>n;
	x[0]=1000000000;
	y[0]=1000000000;
	for(int i=1;i<=n;++i)
		f>>x[i]>>y[i];
	int pi=0,pc=0,go=1;
	for(int i=1;i<=n;++i)
		if(x[i]<x[pi])
            pi=i;
	pc=pi;
	double u=0;
	while(go!=0 or pi!=pc)
	{
		go=0;
		v.push_back(pc);
		double ma=10000;
		int poznoua=pc;
		for(int i=1;i<=n;++i)
		{
			if(verif[i]!=0 or i==pc)
                continue;

			double unghi=atan2(x[i]-x[pc],y[i]-y[pc]);

			if(unghi<0)
                unghi=unghi+2*M_PI;

			unghi=unghi-u;

			if(unghi<0)
                unghi=unghi+2*M_PI;

			if(ma>unghi)
                {
                    ma=unghi;
                    poznoua=i;
                }
		}
		u=atan2(-(x[pc]-x[poznoua]),-(y[pc]-y[poznoua]));
		if(u<0)
            u=u+2*M_PI;
		pc=poznoua;
		verif[pc]=1;
	}
	reverse(v.begin(),v.end());
	g<<v.size()<<endl;
	g<<setprecision(6)<<fixed;
	for(int i=0;i<v.size();++i)
        g<<x[v[i]]<<" "<<y[v[i]]<<endl;
	return 0;
}