Cod sursa(job #1615597)

Utilizator hrazvanHarsan Razvan hrazvan Data 26 februarie 2016 18:15:39
Problema Laser Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <stdio.h>
#include <math.h>
#define MAXN 512
#define EPS 0.00001
#define MY_PI 3.141592653
double st[MAXN], dr[MAXN];
int nr[MAXN], sv[MAXN], dsv, dro;
char state[MAXN];
double o[MAXN];

inline char intersect(double a, double b, double c){
  if(a - b < MY_PI){
    if(c > a && c < b)
      return 1;
    return 0;
  }
  else{
    if(c < a || c > b)
      return 1;
    return 0;
  }
}

inline char interior(double a1, double b1, double a2, double b2){
  if(b1 - a1 < b2 - a2)
    return 0;
  if(b1 - a1 < MY_PI){
    if(a1 < a2 && b1 > b2)
      return 1;
    return 0;
  }
  else{
    if(a2 < a1 && b2 > b1)
      return 1;
    return 0;
  }
}

inline void change(double *a, double *b, double c, double d){
  if((*b) - (*a) < MY_PI){
    if(d - c < MY_PI){
      if(d > (*a) && c < (*b))
        *b = c - EPS;
    }
    else{
      if(c > *a)
        *b = c - EPS;
    }
  }
  else{
    if(d - c < MY_PI){
      if(d > (*b))
        *b = d + EPS;
    }
    else{
      if(d < (*b) && c < (*a))
        *b = c + EPS;
    }
  }
}

void qs(int s, int d){
  int i = s, j = d, aux2;
  double piv = st[(s + d) / 2], aux;
  while(i <= j){
    while(st[i] < piv)
      i++;
    while(st[j] > piv)
      j--;
      if(i <= j){
        aux = st[i];  st[i] = st[j];  st[j] = aux;
        aux = dr[i];  dr[i] = dr[j];  dr[j] = aux;
        aux2 = state[i];  state[i] = state[j];  state[j] = aux2;
        i++;  j--;
      }
  }
  if(s < j)
    qs(s, j);
  if(i < d)
    qs(i, d);
}

int main(){
  FILE *in = fopen("laser.in", "r");
  int n, i, j, x, y;
  double a, b, aux;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &x, &y);
    a = atan2(y, x);
    fscanf(in, "%d%d", &x, &y);
    b = atan2(y, x);
    if(a > b){
      aux = a;  a = b;  b = aux;
    }
    st[i] = a;
    dr[i] = b;
  }
  for(i = 0; i < n; i++)
    fscanf(in, "%d", &state[i]);
  fclose(in);
  qs(0, n - 1);
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      if(i != j)
        if(interior(st[i], dr[i], st[j], dr[j]))
          nr[i]++;
  for(i = 0; i < n; i++){
    sv[dsv] = i;
    dsv++;
    while(dsv > 0 && nr[sv[dsv - 1]] == 0){
      for(j = 0; j < n; j++){
        if(j != sv[dsv - 1]){
          if(state[sv[dsv - 1]]){
            if(intersect(st[j], dr[j], dr[sv[dsv - 1]])){
              state[j] = !state[j];
            }
          }
          if(interior(st[j], dr[j], st[sv[dsv - 1]], dr[sv[dsv - 1]]))
            nr[j]--;
          change(&st[j], &dr[j], st[sv[dsv - 1]], dr[sv[dsv - 1]]);
        }
      }
      if(state[sv[dsv - 1]]){
        state[sv[dsv - 1]] = 0;
        o[dro] = dr[sv[dsv - 1]];
        dro++;
      }
      dsv--;
    }
  }
  FILE *out = fopen("laser.out", "w");
  fprintf(out, "%d\n", dro);
  for(i = 0; i < dro; i++){
    o[i] = o[i] / MY_PI * 180;
    while(o[i] < 0)
      o[i] += 360;
    fprintf(out, "%.5lf\n", o[i]);
  }
  fclose(out);
  return 0;
}