Cod sursa(job #1559333)

Utilizator hrazvanHarsan Razvan hrazvan Data 30 decembrie 2015 16:36:11
Problema Camera Scor 100
Compilator c Status done
Runda Lista lui wefgef Marime 2.66 kb
#include <stdio.h>
#define MAXN 2000
#define INF 2000000000.0
#define EPS 0.0000001
typedef struct{
  double x, y;
}punct;
punct v[MAXN + 2];
punct inf[MAXN + 7], cinf[MAXN + 7];
int dr = 0;

inline double myabs(double x){
  return x < 0 ? -x : x;
}

inline double aria(punct a, punct b, punct c){
  return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}

inline char eq(punct a, punct b){
  if(a.x - b.x <= EPS && a.x - b.x >= -EPS)
    if(a.y - b.y <= EPS && a.y - b.y >= -EPS)
      return 1;
  return 0;
}

inline void getdr(punct a, punct b, double *x, double *y, double *z){
  *x = a.y - b.y;
  *y = b.x - a.x;
  *z = a.x * b.y - a.y * b.x;
}

inline void inters(punct *rez, punct a, punct b, punct c, punct d){
  double a1, b1, c1, a2, b2, c2;
  getdr(a, b, &a1, &b1, &c1);
  getdr(c, d, &a2, &b2, &c2);
  (*rez).x = (b1 * c2 - c1 * b2) / (b2 * a1 - a2 * b1);
  if(b1 != 0)
    (*rez).y = (-c1 - (*rez).x * a1) / b1;
  else
    (*rez).y = (-c2 - (*rez).x * a2) / b2;
}

inline double ec(punct a, punct b, punct c){
  double x, y, z;
  getdr(a, b, &x, &y, &z);
  return c.x * x + c.y * y + z;
}

inline void change(int p, double ar){
  double s;
  s = ec(v[p], v[p + 1], v[p - 1]);
  if(aria(v[p - 1], v[p], v[p + 1]) * ar < 0)
    s = -s;
  int i, j;
  char g = -1;
  punct last;
  j = 0;
  inf[dr] = inf[0];
  for(i = 0; i <= dr; i++){
    if(ec(v[p], v[p + 1], inf[i]) * s >= 0){
      if(g == 0){
        inters(&cinf[j], v[p], v[p + 1], last, inf[i]);
        j++;
      }
      if(i != dr && !(j > 0 && eq(cinf[j - 1], inf[i]))){
        cinf[j] = inf[i];
        j++;
        g = 1;
      }
    }
    else{
      if(g == 1){
        inters(&cinf[j], v[p], v[p + 1], last, inf[i]);
        if(!(j > 0 && eq(cinf[j], cinf[j - 1])))
          j++;
      }
      g = 0;
    }
    last = inf[i];
  }
  for(i = 0; i < j; i++)
    inf[i] = cinf[i];
  dr = j;
}

int main(){
  FILE *in = fopen("camera.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(in, "%lf%lf", &v[i].x, &v[i].y);
  v[n] = v[0];
  v[n + 1] = v[1];
  double ar = 0.0;
  punct zero;
  zero.x = zero.y = 0;
  for(i = 0; i < n; i++)
    ar += aria(zero, v[i], v[i + 1]);
  inf[0].x = -INF;  inf[0].y = -INF;
  inf[1].x = INF;  inf[1].y = -INF;
  inf[2].x = INF;  inf[2].y = INF;
  inf[3].x = -INF;  inf[3].y = INF;
  dr = 4;
  for(i = 0; i < n; i++)
    change(i + 1, ar);
  inf[dr] = inf[0];
  ar = 0;
  for(i = 0; i < dr; i++)
    ar += aria(zero, inf[i], inf[i + 1]);
  FILE *out = fopen("camera.out", "w");
  fprintf(out, "%.2lf", myabs(ar / 2));
  fclose(out);
  return 0;
}