Cod sursa(job #2808791)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 25 noiembrie 2021 16:00:01
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.32 kb
/*#include <bits/stdc++.h>

using namespace std;

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

const int N = 1.2e5 + 1;
int n, punct_initial, cur, poznoua, ver[N];
double x[N], y[N], ma, unghi, last;
vector<int> ans;
bool misca = 1;

int main(){
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> x[i] >> y[i];

    f.close();
    x[0] = y[0] = 1e9;
    for(int i = 1; i <= n; i++){
        if(x[i] < x[punct_initial])
            punct_initial = i;
    }

    cur = punct_initial;
    while(misca || punct_initial != cur){
        misca = 0; // doar la inceput si sfarsit vom trece prin punctul initial (nu il vom include a doua oara in vector)
        ans.push_back(cur);
        ma = 10000;
        poznoua = cur; // poznoua = urm. punct
        for(int i = 1; i <= n; i++){
            if(ver[i] || i == cur) // nu ne intereseaza puncte deja vizitate (verificam si i == cur pentru prima iteratie)
                continue;

            unghi = atan2(x[i] - x[cur], y[i] - y[cur]); // facem diferenta pt. ca atan2 returneaza unghiul facut cu centrul => consideram centrul sa fie punctul curent
            //cout << i << ' ' << cur << " ----- " << last / M_PI * 180 << "  ";
            if(unghi < 0)
                unghi += 2 * M_PI;

            //cout << unghi / M_PI * 180 << "  ";
            unghi -= last;
            if(unghi < 0)
                unghi += 2 * M_PI;

            //cout << unghi / M_PI * 180 << '\n';
            if(ma > unghi)
                ma = unghi, poznoua = i;
        }

        last = atan2(x[poznoua] - x[cur], y[poznoua] - y[cur]);
        if(last < 0)
            last += 2 * M_PI;

        cur = poznoua;
        ver[cur] = 1;
    }

    reverse(ans.begin(), ans.end()); // vrem punctele in ordine trigonometrica
    cout << ans.size() << '\n';
    for(int i: ans)
        cout << x[i] << ' ' << y[i] << '\n';

    g.close();
}*/

#include<stdio.h>

#include<vector>

#include<math.h>

#include <algorithm>

#define pb push_back



const int maxn = 120000;



using namespace std;



vector<int> VECT;

double X[maxn],Y[maxn];

int N,VER[maxn];



int main()

{

	freopen("infasuratoare.in","r",stdin);

	freopen("infasuratoare.out","w",stdout);

	scanf("%d\n",&N);

	X[0] = 1000000000;Y[0] = 1000000000;

	for(int i = 1;i <= N; ++i)

		scanf("%lf %lf\n",&X[i],&Y[i]);

	int punct_initial = 0;

	int cur = 0;

	int move = 1;

	for(int i = 1;i <= N; ++i)

		if (X[i] < X[punct_initial]) punct_initial = i;

	cur = punct_initial;

	double last = 0;

	while(move || punct_initial != cur)

	{

		move = 0;

		VECT.pb(cur);

		double ma = 10000;

		int poznoua = cur;

		for(int i = 1;i <= N; ++i)

		{

			if (VER[i] || i == cur) continue;

			double unghi = atan2((X[i] - X[cur]),Y[i] - Y[cur]);

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

			unghi -= last;

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

			if (ma > unghi) {ma = unghi; poznoua = i;}

		}

		last = atan2(-(X[cur] - X[poznoua]),-(Y[cur] - Y[poznoua]));

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

		cur = poznoua;

		VER[cur] = 1;

	}

	reverse(VECT.begin(),VECT.end());

	printf("%d\n",VECT.size());

	for(unsigned int i = 0;i < VECT.size(); ++i)

		printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);

	return 0;

}