Pagini recente » Cod sursa (job #1657945) | Cod sursa (job #1920543) | Cod sursa (job #2806069) | Cod sursa (job #1373731) | Cod sursa (job #3041843)
#include<fstream>
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz, c, ind, ok, use[120005];
double unghi, u, z, x[120005], y[120005];
vector<int> ans;
int main()
{
fin >> n;
for(int i = 1; i <= n; ++ i)
fin >> x[i] >> y[i];
ind = 1;
for(int i = 2; i <= n; ++ i)
if(x[i] < x[ind])
ind = i;
c= ind;
ok = 1;
u = 0;
while(ok || ind != c)
{
ok = 0;
z = 100001;
poz = c;
ans.push_back(c);
for(int i = 1; i <= n; ++ i)
{
if(use[i] || i == c)
continue;
unghi = atan2((x[i] - x[c]), (y[i] - y[c]));
if(unghi < 0)
unghi += 2 * M_PI;
unghi -= u;
if(unghi < 0)
unghi += 2 * M_PI;
if(z > unghi)
{
z = unghi;
poz = i;
}
}
u = atan2(-(x[c] - x[poz]), -(y[c] - y[poz]));
if(u < 0)
u += 2 * M_PI;
c = poz;
use[c] = 1;
}
int h = ans.size();
fout << h << '\n';
reverse(ans.begin(), ans.end());
for(int i = 0; i < h; ++ i)
fout<< fixed << setprecision(6) << x[ans[i]] << ' ' << y[ans[i]] << '\n';
return 0;
}