Pagini recente » Cod sursa (job #1435536) | Cod sursa (job #1999991) | Cod sursa (job #351315) | Cod sursa (job #2107045) | Cod sursa (job #2439294)
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
# define M_PI 3.14159265358979323846
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 120005;
const int inf = 1000000006;
int n,initial;
bool viz[NMAX];
struct point{
double x,y;
}v[NMAX], posmin;
vector<int> Vector;
int main(){
int i;
f >> n;
posmin.x = inf;
for(i = 1 ; i <= n ; i++){
f >> v[i].x >> v[i].y;
if(v[i].x < posmin.x){
initial = i;
posmin = v[i];
}else
if(v[i].x == posmin.x && v[i].y < posmin.y){
initial = i;
posmin = v[i];
}
}
bool move = 1;
int actual = initial;
double last = 0;
while(move || actual != initial){
move = 0;
Vector.push_back(actual);
int newpos = actual;
double ma = 10005;
for(i = 1 ; i <= n ; i++){
if(viz[i] || i == actual)
continue;
double unghi = atan2(v[i].x - v[actual].x , v[i].y - v[actual].y);
if(unghi < 0)
unghi += 2 * M_PI;
unghi -= last;
if(unghi < 0)
unghi += 2 * M_PI;
if(unghi < ma){
ma = unghi;
newpos = i;
}
}
last = atan2(v[newpos].x - v[actual].x, v[newpos].y - v[actual].y);
if(last < 0)
last += 2 * M_PI;
actual = newpos;
viz[actual] = 1;
}
reverse(Vector.begin(), Vector.end());
g << Vector.size() << "\n";
for(auto it: Vector)
g << fixed << setprecision(6) << v[it].x << " " << v[it].y << "\n";
return 0;
}