Cod sursa(job #1546383)

Utilizator hrazvanHarsan Razvan hrazvan Data 7 decembrie 2015 23:18:26
Problema Rubarba Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <stdio.h>
#include <math.h>
#define MAXN 100000
#define INF 2000000000
#define INFMARE 2000000000000000.0
typedef struct{
  int x, y;
}punct;
punct v[MAXN];
int sv[4 * MAXN + 1];

inline long long aria(punct a, punct b, punct c){
  return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}

void qs(int st, int dr){
  int i = st, j = dr;
  punct piv = v[(st + dr) / 2], aux;
  while(i <= j){
    while(aria(v[0], v[i], piv) > 0)
      i++;
    while(aria(v[0], piv, v[j]) > 0)
      j--;
    if(i <= j){
      aux = v[i];  v[i] = v[j];  v[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

inline double coordox(int p, int x){
  double rad = atan2(v[sv[p - 1]].y - v[sv[p]].y, v[sv[p - 1]].x - v[sv[p]].x);
  rad = 2 * M_PI - rad;
  while(rad > 2 * M_PI)
    rad -= 2 * M_PI;
  double a = cos(rad);
  double b = sin(rad);
  double x0 = (v[sv[x]].x - v[sv[p]].x) * a - (v[sv[x]].y - v[sv[p]].y) * b;
  return -x0;
}

inline double coordoy(int p, int x){
  double rad = atan2(v[sv[p - 1]].y - v[sv[p]].y, v[sv[p - 1]].x - v[sv[p]].x);
  rad = 2 * M_PI - rad;
  double a = cos(rad);
  double b = sin(rad);
  double y0 = (v[sv[x]].y - v[sv[p]].y) * a + (v[sv[x]].x - v[sv[p]].x) * b;
  return -y0;
}

int main(){
  FILE *in = fopen("rubarba.in", "r");
  int n, i, p;
  punct m;
  m.x = m.y = INF;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &v[i].x, &v[i].y);
    if(m.x > v[i].x || (m.x == v[i].x && m.y > v[i].y)){
      m = v[i];
      p = i;
    }
  }
  fclose(in);
  punct aux;
  aux = v[0];  v[0] = v[p];  v[p] = aux;
  qs(1, n - 1);
  int dr = 2;
  sv[0] = 0;
  sv[1] = 1;
  for(i = 2; i < n; i++){
    while(dr > 2 && aria(v[sv[dr - 2]], v[sv[dr - 1]], v[i]) < 0)
      dr--;
    sv[dr] = i;
    dr++;
  }
  for(i = dr; i < 4 * dr; i++)
    sv[i] = sv[i - dr];
  sv[2 * dr] = sv[0];
  int p1 = 0, p2 = 0, p3 = 0;
  double rez = INFMARE;
  for(i = 1; i < n; i++){
    if(coordox(1, i) < coordox(1, p1))
      p1 = i;
    if(coordox(1, i) > coordox(1, p3))
      p3 = i;
    if(coordoy(1, i) > coordoy(1, p2))
      p2 = i;
  }
  double a, b, c;
  for(i = 1; i <= n; i++){
    while(coordox(i, p1 + 1) < coordox(i, p1))
      p1++;
    while(coordox(i, p3 + 1) > coordox(i, p3))
      p3++;
    while(coordoy(i, p2 + 1) > coordoy(i, p2))
      p2++;
    a = coordox(i, p1);
    b = coordoy(i, p2);
    c = coordox(i, p3);
    if(b * (c - a) < rez)
      rez = b * (c - a);
  }
  FILE *out = fopen("rubarba.out", "w");
  fprintf(out, "%.2lf", rez);
  fclose(out);
  return 0;
}