Pagini recente » Borderou de evaluare (job #2024061) | Borderou de evaluare (job #2496320) | Borderou de evaluare (job #594654) | Borderou de evaluare (job #1234034) | Cod sursa (job #2412662)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#define ld long double
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair<ld,ld> v[120001];
bool viz[120001];
vector<int> ans;
int main()
{
ld PI = 2*asin(1);
f >> n;
for(int i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
int poz = 0, act = 0, ok = 1;
v[0].x = v[0].y = 1000000000;
for(int i = 1; i <= n; ++i)
if(v[i].x < v[poz]. x) poz = i;
act = poz;
ld last = 0;
while(ok || act != poz)
{
ok = 0;
ans.push_back(act);
int neww = act;
ld ma = 10000;
for(int i = 1; i <= n; ++i)
{
if(viz[i] || i == act) continue;
ld unghi = atan2( (v[i].x - v[act].x), v[i].y-v[act].y);
if(unghi < 0) unghi += 2* PI;
unghi -= last;
if(unghi < 0) unghi += 2* PI;
if(ma > unghi)
{
ma = unghi;
neww = i;
}
}
last = atan2( v[neww].x- v[act].x, v[neww].y - v[act].y );
if(last < 0) last += 2* PI;
act = neww;
viz[act] = 1;
}
reverse(ans.begin(), ans.end());
g << ans.size() << '\n' << setprecision(6) << fixed;
for(int i = 0; i < ans.size(); ++i)
g << v[ans[i] ].x << ' ' << v[ans[i]].y << '\n';
f.close();
g.close();
return 0;
}