Cod sursa(job #3132774)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 23 mai 2023 21:13:03
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <bits/stdc++.h>
#define L 100005
#define INF 1000000005
#define EPS 0.00000000001
#define CORNERS 4
using namespace std;

struct MS{
  long double x;
  long double y;
};

int n, k, l;
MS v[L], corn[CORNERS];
int st[L], ind;
vector <int> hull;
long double min_angle = 4;

bool cmp(const MS &a, const MS &b){
  return a.x < b.x;
}

long double area(int i1, int i2, int i3){
  long double a = v[i1].x;
  long double b = v[i1].y;
  long double c = v[i2].x;
  long double d = v[i2].y;
  long double e = v[i3].x;
  long double f = v[i3].y;
  return (a * d + b * e + c * f  - a * f - b * c - d * e) / 2;
}

void generate_convex_hull(){
  sort (v + 1, v + n + 1, cmp);
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) > -EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = ind - 1; i > 0; i--)
    hull.push_back(st[i]);
  ind = 0;
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) < EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = 0; i < ind - 1; i++)
    hull.push_back(st[i]);
}

void generate_corners(){
  corn[0].x = -l;
  corn[0].y = -l;
  corn[1].x = -l;
  corn[1].y = l;
  corn[2].x = l;
  corn[2].y = -l;
  corn[3].x = l;
  corn[3].y = l;
}

void rotate_hull(){
  for (int i = 1; i <= n; i++){
    int x = - v[i].y;
    int y = v[i].x;
    v[i].x = x;
    v[i].y = y;
  }
}

long double get_angle(long double x1, long double y1, long double xo, long double yo, long double x2, long double y2){
  long double angle1 = atan2(x1 - xo, y1 - yo);
  long double angle2 = atan2(x2 - xo, y2 - yo);
  long double dif_angle = abs(angle1 - angle2);
  long double pi = atan2(0, -1);
  if (dif_angle > pi)
    dif_angle = 2 * pi - dif_angle;
  return dif_angle;
}

int main(){
  cin >> n >> k >> l;
  for (int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;

  generate_convex_hull();

  generate_corners();
  for (int t = 0; t < CORNERS; t++){
    int x = corn[t].x;
    int y = corn[t].y;
    long double max_angle = -4;
    for (int i = 0; i < (int)hull.size(); i++){
      int j = (i + 1) % hull.size();
      long double angle = get_angle(v[hull[i]].x, v[hull[i]].y, x, y, v[hull[j]].x, v[hull[j]].y);
      max_angle = max(max_angle, angle);
    }
    min_angle = min(min_angle, max_angle);
  }

  for (int rot = 0; rot < 4; rot++){
    rotate_hull();
    for (int i = 0; i < (int)hull.size(); i++){
      int j = (i + 1) % hull.size();
      long double x_a = v[hull[i]].x;
      long double y_a = v[hull[i]].y;
      long double x_b = v[hull[j]].x;
      long double y_b = v[hull[j]].y;
      long double x, y = -l;
      if (abs(y_b - y_a) < EPS)
        x = INF;
      else
        x = x_a + (x_a - x_b) * (y_a + l) / (y_b - y_a);
      if (x < -l || x > l)
        x = INF;
      if (abs(x - INF) > EPS){
        int le = i, ri = i + 1 + hull.size(), best = -1;
        while (le <= ri){
          int t1 = le + (ri - le) / 3;
          int t2 = le + (ri - le) / 3 * 2;
          long double angle_1 = get_angle(x_a, y_a, x, y, v[hull[t1 % hull.size()]].x, v[hull[t1 % hull.size()]].y);
          long double angle_2 = get_angle(x_a, y_a, x, y, v[hull[t2 % hull.size()]].x, v[hull[t2 % hull.size()]].y);
          if (angle_1 < angle_2){
            le = t1 + 1;
            best = t2;
          }
          else{
            ri = t2 - 1;
            best = t1;
          }
        }
        long double max_angle = get_angle(x_a, y_a, x, y, v[hull[best % hull.size()]].x, v[hull[best % hull.size()]].y);
        min_angle = min(min_angle, max_angle);
      }
    }
  }

  cout << min_angle << "\n";
  return 0;
}