Cod sursa(job #2961511)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 6 ianuarie 2023 16:42:01
Problema Rubarba Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.7 kb
#include <iomanip>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#define MAXN 100000
#define MAXVAL 1000000

#define DEBUG 0

using namespace std;

struct Point{
  double x;
  double y;
  int id;
};

struct Edge{
  double a;
  double b;
};

struct SortEdge{
  double upper;
  double lower;
  bool minus;

  Point end;
};

Point getIntersection(Edge e1, Edge e2){
  Point r;
  r.x = (e2.b - e1.b) / (e1.a - e2.a);
  r.y = e1.a * r.x + e1.b;

  return r;
}

Point getProjection(Point p, Edge e){
  Edge pp;
  pp.a = -1 / e.a;
  pp.b = p.y - pp.a * p.x;

  //printf(" --- %.2f  %.2f --- \n", pp.a, pp.b);
  return getIntersection(e, pp);
}

Edge getEdge(Point p1, Point p2){
  Edge r;
  if(p1.x == p2.x){
    r.a = MAXVAL;
    r.b = p1.x;
    return r;
  }

  r.a = (p1.y - p2.y) / (p1.x - p2.x);
  r.b = p1.y - r.a * p1.x;

  return r;
}

double getDistance(Point p1, Point p2){
  long double difx = p1.x - p2.x;
  long double dify = p1.y - p2.y;
  return sqrt(difx * difx + dify * dify);
}

// Returneaza true daca a trebuie pus inainte de b
bool sortCompare(SortEdge a, SortEdge b){
  if(a.minus && !b.minus)
    return true;
  if(!a.minus && b.minus)
    return false;

  double left = a.upper * b.lower;
  double right = a.lower * b.upper;

  if(a.minus && b.minus)
    return left > right;

  return left < right;;
}

/*
  1 - trigonometric 
  0 - colineare
 -1 - clockwise
*/
int getOrder(Point a, Point b, Point c){
  int left = (a.y - b.y) * (b.x - c.x); 
  int right = (b.y - c.y) * (a.x - b.x);

  if(left > right)
    return 1;
  if(right == left)
    return 0;
  return -1;
}

Point p[MAXN], r[MAXN], u[MAXN];
SortEdge v[MAXN];

int main(){
  int n, i, j, dr, mini;
  double min, minx, maxx, miny, maxy, maxd, dist;

  ifstream fin ("rubarba.in");
  fin >> n;
  
  min = MAXVAL;
  mini = 0;
  miny = MAXVAL;
  maxy = MAXVAL;
  minx = -MAXVAL;
  maxx = -MAXVAL;

  for(i = 0; i < n; i ++){
    fin >> p[i].x >> p[i].y;
    p[i].id = i + 1;

    if(p[i].y < min){
      min = p[i].y;
      mini = i;
    }

    if(p[i].y < miny)
      miny = p[i].y;
    if(p[i].y > maxy)
      maxy = p[i].y;
    if(p[i].x < minx)
      minx = p[i].x;
    if(p[i].x > maxx)
      maxx = p[i].x;
  }
  fin.close();

  // Punem punctul de y minim la pozitia p[0]
  Point aux = p[mini];
  p[mini] = p[0];
  p[0] = aux;

  // Ordonam punctele in ordinea pantei dreptei
  for(i = 1; i < n; i ++){
    v[i - 1].end = p[i];
    v[i - 1].upper = p[i].y - p[0].y;
    v[i - 1].lower = p[i].x - p[0].x;

    if(v[i - 1].lower < 0){
      v[i - 1].lower = - v[i - 1].lower;
      v[i - 1].minus = true;
    }
  }

  sort(v, v + n - 1, sortCompare);

  if(DEBUG){
    for(i = 0; i < n - 1; i++){
      printf("%d: ", v[i].end.id);
      if(v[i].minus)
        printf("- ");
      else
        printf("  ");
      printf("%.1f %.1f\n", v[i].upper, v[i].lower);
    }
    printf("\n");
  }

  /// Reordonam punctele in ordinea corecta a infasuratorii convexe
  u[0] = p[0];
  i = 0;
  while(v[i].minus)
    i ++;

  j = 1;
  while(i < n-1){
    u[j] = v[i].end;
    i ++;
    j ++;
  }

  i = 0;
  while(j < n){
    u[j] = v[i].end;
    i ++;
    j ++;
  }

  if(DEBUG){
    for(i = 0; i < n; i ++){
      printf("%d ", u[i].id);
    }
    printf("\n");
  }

  // Determinam infasuratoarea convexa
  r[0] = u[0];
  r[1] = u[1];
  dr = 2;

  for(i = 2; i < n; i ++){
    while(dr > 1 && getOrder(r[dr - 2], r[dr - 1], u[i]) != -1)
      dr --;

    r[dr] = u[i];
    dr ++;
  }

  if(DEBUG){
    for(i = 0; i < dr; i ++){
      printf("%d ", r[i].id);
    }
    printf("\n\n");
  }

  // Determinam dreptunghiul minim care sa contina infasuratoarea convexa
  Edge base;
  Point prj;
  Point minxi, maxxi;

  min = (maxx - minx) * (maxy - miny);
  for(i = 0; i < dr; i ++){
    minx = MAXVAL;
    maxx = -MAXVAL;
    maxd = 0;
    base = getEdge(r[i], r[(i + 1) % dr]); // Luam latura de baza

    if(DEBUG)
      printf("%d - %d:\n", r[i].id, r[(i + 1) % dr].id);

    if(base.a != MAXVAL && base.a != 0){

      for(j = 0; j < dr; j ++){
        prj = getProjection(r[j], base);
        if(DEBUG)
          printf("proiectie %d  -  (%.2f, %.2f)\n", r[j].id, prj.x, prj.y);

        if(prj.x < minx){
          minx = prj.x;
          minxi = prj;
        }
        if(prj.x > maxx){
          maxx = prj.x;
          maxxi = prj;
        }

        dist = getDistance(prj, r[j]);
        if(dist > maxd)
          maxd = dist;
      }

      // Dist este aria
      dist = maxd * getDistance(maxxi, minxi);
      if(min == -1 || min > dist)
        min = dist;

      if(DEBUG)
        printf("%.2f = %.2f * %.2f\n\n", dist, maxd, getDistance(maxxi, minxi));
    }
  }

  ofstream fout ("rubarba.out");
  fout << fixed;
  fout << setprecision(2);
  fout << min << endl;
  fout.close();
  return 0;
}