Cod sursa(job #678140)

Utilizator juniorOvidiu Rosca junior Data 11 februarie 2012 06:32:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#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], nou;

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 primul = 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 (primul || punct_initial != curent) {
    primul = 0;
    VECT.pb(curent);
    double ma = 10000;
    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; nou = i;
      }
    }
    last = atan2(X[nou] - X[curent], Y[nou] - Y[curent]);
    if (last < 0)
      last += 2 * M_PI;
    VER[nou] = 1;
    curent = nou;
  }
  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;
}