Pagini recente » Cod sursa (job #190711) | Cod sursa (job #2300518) | Cod sursa (job #2820841) | Cod sursa (job #1468397) | Cod sursa (job #678136)
Cod sursa(job #678136)
#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 curent = 0;
//int move = 1;
for (int i = 1; i <= N; ++i) // "in caz de egalitate cel mai de jos" ?
if (X[i] < X[punct_initial])
punct_initial = i;
curent = punct_initial;
double last = 0;
while(/*move || */punct_initial != curent) {
//move = 0;
VECT.pb(curent);
double ma = 10000;
int poznoua = curent;
for (int i = 1; i <= N; ++i) {
if (VER[i] || i == curent)
continue;
double unghi = atan2((X[i] - X[curent]), Y[i] - Y[curent]);
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[curent] - X[poznoua]), -(Y[curent] - Y[poznoua]));
if (last < 0)
last += 2 * M_PI;
curent = poznoua;
VER[curent] = 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;
}