Pagini recente » Cod sursa (job #1995083) | Cod sursa (job #2660632) | Cod sursa (job #2489279) | Cod sursa (job #2052369) | Cod sursa (job #861156)
Cod sursa(job #861156)
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define MAXN 120050
int N;
double X[MAXN], Y[MAXN];
bool used[MAXN];
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%lf %lf", &X[i], &Y[i]);
int first = 0;
for(int i = 0; i < N; i++)
if(Y[i] < Y[first])
first = i;
vector<int> parc;
int crt = first;
bool ok = true;
double last = 0.0;
while(crt != first || ok) {
ok = false;
int pmin = -1;
parc.push_back(crt);
double vmin = M_PI * 3;
for(int i = 0; i < N; i++)
if(!used[i] && i != crt) {
double unghi = atan2(Y[i] - Y[crt], X[i] - X[crt]);
if(unghi < 0)
unghi += 2 * M_PI;
unghi -= last;
if(unghi < 0)
unghi += 2 * M_PI;
if(unghi < vmin) {
vmin = unghi;
pmin = i;
}
}
last = vmin;
used[pmin] = true;
crt = pmin;
}
printf("%d\n", (int)parc.size());
for(vector<int> :: iterator it = parc.begin(); it != parc.end(); it++)
printf("%.6lf %.6lf\n", X[*it], Y[*it]);
return 0;
}