Cod sursa(job #1559188)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 decembrie 2015 13:59:56
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#define nmax 120005
#include <math.h>

using namespace std;


struct pereche{
  double x,y;
};

int N,start;
pereche V[nmax];
vector <int> Rez;
bool viz[nmax];

int main(){
  freopen("infasuratoare.in","r",stdin);
  freopen("infasuratoare.out","w",stdout);
  scanf("%d ",&N);
  int i,t,poznoua;
  bool m = true;
  double x,y,unghi,lst = 0,ma;
  for(i = 1;i <= N;++i){
    scanf("%lf %lf ",&V[i].x,&V[i].y);
    if(i == 1 || V[start].x > V[i].x || (V[start].x == V[i].x && V[start].y > V[i].y))
       start = i;
  }
  t = start;
  
  while(m == true || t != start){  ///folosim variabila m pentru a intra in bucla

    Rez.push_back(t);
    
    ma = 10000;
    m = false;
    poznoua = t;

    for(i = 1;i <= N;++i){
      if(viz[i] == true || t == i)continue;
      unghi = atan2(V[i].x - V[t].x,V[i].y - V[t].y);
      if(unghi < 0)unghi += 2*M_PI;
      unghi -= lst;  ///scadem unghiul cu care s-a intors varful curent fata de varful precedent
      if(unghi < 0)unghi += 2*M_PI;
      if(ma > unghi){     ///actualizam unghiul maxim gasit(ma) si varful pentru care a fost gasita aceasta valoare
        ma = unghi;
        poznoua = i;
      }

    }
    lst = atan2(V[poznoua].x - V[t].x,V[poznoua].y - V[t].y);  ///calculam noul unghi (relativ)
    if(lst < 0)lst += 2*M_PI;
    t = poznoua;
    viz[t] = true;
  }
  
  
  printf("%d\n",Rez.size());
  for(i = Rez.size() - 1;i >= 0;i--)printf("%lf %lf\n",V[Rez[i]].x,V[Rez[i]].y);
  printf("\n");

  return 0;
}