Cod sursa(job #678138)

Utilizator juniorOvidiu Rosca junior Data 11 februarie 2012 06:17:18
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 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], poznoua;

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;
    //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;
}