Cod sursa(job #1615484)

Utilizator hrazvanHarsan Razvan hrazvan Data 26 februarie 2016 17:01:35
Problema Laser Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.99 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];

void qs(int s, int d){
  int i = s, j = d, 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;
        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(st[j] >= st[i] && dr[j] <= dr[i])
          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(st[j] <= st[sv[dsv - 1]] && dr[j] >= st[sv[dsv - 1]]){
              state[j] = !state[j];
            }
          }
          if(st[j] <= st[sv[dsv - 1]] && dr[j] >= dr[sv[dsv - 1]])
            nr[j]--;
          if(dr[j] >= st[sv[dsv - 1]] && dr[j] <= dr[sv[dsv - 1]])
            dr[j] = st[sv[dsv - 1]] - EPS;
        }
      }
      if(state[sv[dsv - 1]]){
        state[sv[dsv - 1]] = 1;
        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 * 360 + 360;
    while(o[i] >= 360)
      o[i] -= 360;
    fprintf(out, "%lf\n", o[i]);
  }
  fclose(out);
  return 0;
}