Pagini recente » Cod sursa (job #876479) | Cod sursa (job #2331747) | Cod sursa (job #544445) | Cod sursa (job #2694047) | Cod sursa (job #1191369)
// naiv -- O(n^2)
#include <fstream>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
const int Nmax = 120005;
double X[Nmax], Y[Nmax];
char used[Nmax];
vector<int> hull;
int main()
{
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int N;
f >> N;
for (int i = 0; i < N; i++)
f >> X[i] >> Y[i];
int start = 0;
for (int i = 0; i < N; i++)
if (X[start] > X[i] || (X[start] == X[i] && Y[start] > Y[i]))
start = i;
int cur = start;
double last_angle = M_PI * 3/2;
double current_angle = 0;
while(hull.empty() || cur != start)
{
double best_angle = 1000;
int candidate = -1;
for (int i = 0; i < N; i++)
{
if (i == cur || used[i]) continue;
double new_angle = atan2(Y[i] - Y[cur], X[i] - X[cur]);
if (new_angle < 0)
new_angle += 2*M_PI;
double angle = new_angle - last_angle;
if (angle < 0)
angle += 2*M_PI;
if (angle < best_angle)
{
best_angle = angle;
candidate = i;
current_angle = new_angle;
}
}
last_angle = current_angle;
hull.push_back(candidate);
used[candidate] = 1;
cur = candidate;
}
g << hull.size() << '\n';
g << X[hull.back()] << ' ' << Y[hull.back()] << '\n';
hull.pop_back();
for (int i: hull)
g << X[i] << ' ' << Y[i] << '\n';
return 0;
}