Cod sursa(job #1723581)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 iunie 2016 23:23:54
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N_MAX = 100005;

struct Point {
  double x, y;
  Point() {}
  inline bool operator <(const Point &o) const { return (x == o.x ? y < o.y : x < o.x); }
};

struct Line {
  double a;
  double b;
  double c;
  Line() {}
};

int N;
Point P[N_MAX];

Line fromSegment(Point p1, Point p2) {
  Line L;
  L.a = p1.y - p2.y;
  L.b = p2.x - p1.x;
  L.c = (-1) * (L.a * p1.x) + (-1) * (L.b * p1.y);
  return L;
}

Line fromSlope(double m, Point p) {
  Line L;
  L.a = m * (-1);
  L.b = 1;
  L.c = m * p.x - p.y;
  return L;
}

Point Cross(Line L1, Line L2) {
  Point p;
  p.x = (L2.b * L1.c - L1.b * L2.c) / (L2.a * L1.b - L2.b * L1.a);
  p.y = (L1.a * L2.c - L2.a * L1.c) / (L2.a * L1.b - L2.b * L1.a);
  return p;
}

double Det(Point A, Point B, Point C) {
  return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

double distPoints(Point A, Point B) {
  return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}

double distLine(Point P, Line L) {
  return fabs(L.a * P.x + L.b * P.y + L.c) / sqrt(L.a * L.a + L.b * L.b);
}

void getConvex() {
  Point H[N_MAX];
  int Stack[N_MAX], Size = 0, Top;
  
  sort(P+1, P+N+1);
  Stack[1] = 1; Stack[2] = 2; Top = 2;
  for(int i = 3; i <= N; i++) {
    while(Top > 1 and Det(P[Stack[Top - 1]], P[Stack[Top]], P[i]) < 0LL) Top--;
    Stack[++Top] = i;
  }
  for(int i = 1; i < Top; i++) H[i] = P[Stack[i]];
  Size += Top - 1;
  
  Stack[1] = N; Stack[2] = N - 1; Top = 2;
  for(int i = N - 2; i > 0; i--) {
    while(Top > 1 and Det(P[Stack[Top - 1]], P[Stack[Top]], P[i]) < 0LL) Top--;
    Stack[++Top] = i;
  }
  for(int i = 1; i < Top; i++) H[Size + i] = P[Stack[i]];
  Size += Top - 1;
  
  N = Size;
  for(int i = 1; i <= N; i++) {
    P[i] = H[i];
    P[N + i] = H[i];
  }
}

int main() {
  freopen("rubarba.in", "r", stdin);
  freopen("rubarba.out", "w", stdout);
  
  scanf("%d", &N);
  for(int i = 1; i <= N; i++) {
    scanf("%lf %lf", &P[i].x, &P[i].y);
  }
  
  getConvex();
  
  printf("The convex hull:\n");
  for(int i = 1; i <= N; i++)
    printf("%f %f\n", P[i].x, P[i].y);
  printf("\n");
  
  double Best = 1e20;
  for(int i = 1; i <= N; i++) {
    Line AB, BC, CD, AD, Perpendicular;
  
    AB = fromSegment(P[i], P[i + 1]);
    
    int farUp, farLeft, farRight;
    double bestUp = 0, bestLeft = 0, bestRight = 0;
    
    for(int j = 1; j <= N; j++) {
      double D = distLine(P[j], AB);
      if(bestUp < D) {
        bestUp = D;
        farUp = j;
      }
    }
    
    CD = fromSlope(-AB.a / AB.b, P[farUp]);
    Perpendicular = fromSlope(AB.b / AB.a, P[i]);
    
    for(int j = 1; j <= farUp; j++) {
      double D = distLine(P[j], Perpendicular);
      if(bestLeft < D) {
        bestLeft = D;
        farLeft = j;
      }
    }
    
    for(int j = farUp + 1; j <= N; j++) {
      double D = distLine(P[j], Perpendicular);
      if(bestRight < D) {
        bestRight = D;
        farRight = j;
      }
    }
    
    AD = fromSlope(AB.b / AB.a, P[farLeft]);
    BC = fromSlope(AB.b / AB.a, P[farRight]);
    
    Point A = Cross(AB, AD);
    Point B = Cross(AB, BC);
    Point C = Cross(BC, CD);
    Point D = Cross(CD, AD);
    
    printf("Currently: I (%d), J(%d), K(%d), L(%d)\n", i, farUp, farLeft, farRight);
    printf("%f %f --> A \n", A.x, A.y);
    printf("%f %f --> B \n", B.x, B.y);
    printf("%f %f --> C \n", C.x, C.y);
    printf("%f %f --> D \n", D.x, D.y);
    printf("The area is %f\n\n", distPoints(A, B) * distPoints(A, D));
    
    Best = min(Best, distPoints(A, B) * distPoints(A, D));
  }
  
  printf("%.8f\n", Best);
  return 0;
}