Submission #44044

#	Time	Username	Problem	Language	Result	Execution time	Memory
44044		wxh010910	Fences (JOI18_fences)	C++17	100 / 100	136 ms	2408 KiB

fences

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 420;
const double eps = 1e-6;
const double inf = 1e9;

inline int Sgn(double x) {
  return fabs(x) < eps ? 0 : x > 0 ? 1 : -1;
}

inline int Cmp(double x, double y) {
  return Sgn(x - y);
}

inline bool Mid(double l, double r, double mid) {
  return Cmp(l, mid) * Cmp(r, mid) <= 0;
}

struct Point {
  double x, y;
  
  Point(double _x = 0, double _y = 0) {
    x = _x, y = _y;
  }
  
  Point operator + (const Point &b) const {
    return Point(x + b.x, y + b.y);
  }
  
  Point operator - (const Point &b) const {
    return Point(x - b.x, y - b.y);
  }
  
  Point operator * (const double &b) const {
    return Point(x * b, y * b);
  }
  
  Point operator / (const double &b) const {
    return Point(x / b, y / b);
  }
  
  double operator * (const Point &b) const {
    return x * b.x + y * b.y;
  }
  
  double operator ^ (const Point &b) const {
    return x * b.y - y * b.x;
  }
  
  bool operator == (const Point &b) const {
    return !Cmp(x, b.x) && !Cmp(y, b.y);
  }
  
  bool operator != (const Point &b) const {
    return Cmp(x, b.x) || Cmp(y, b.y);
  }
  
  inline double Len() {
    return x * x + y * y;
  }
} s(0, 0), t(1, 1000), r[4], p[N], q[N];

double ans, dis[N][N];
int n, m;

inline double Dis(Point x, Point y) {
  return sqrt((x - y).Len());
}

inline bool Mid(Point l, Point r, Point mid) {
  return Mid(l.x, r.x, mid.x) && Mid(l.y, r.y, mid.y);
}

inline Point Projection(Point p, Point q, Point x) {
  Point delta = q - p;
  return p + delta * ((x - p) * delta / delta.Len());
}

inline bool IntersectInterval(double l1, double r1, double l2, double r2) {
  if (l1 > r1) {
    swap(l1, r1);
  }
  if (l2 > r2) {
    swap(l2, r2);
  }
  return Cmp(r1, l2) > 0 && Cmp(r2, l1) > 0;
}

inline bool IntersectSegment(Point l1, Point r1, Point l2, Point r2) {
  if (!IntersectInterval(l1.x, r1.x, l2.x, r2.x) || !IntersectInterval(l1.y, r1.y, l2.y, r2.y)) {
    return false;
  }
  return Sgn((l2 - l1) ^ (r2 - l1)) * Sgn((l2 - r1) ^ (r2 - r1)) < 0 && Sgn((l1 - l2) ^ (r1 - l2)) * Sgn((l1 - r2) ^ (r1 - r2)) < 0;
}

inline bool Check(Point x, Point y) {
  for (int i = 0; i < 4;  ++i) {
    if (IntersectSegment(x, y, r[i], r[i + 1 & 3])) {
      return false;
    }
  }
  Point z = (x + y) / 2;
  if (z.x > -m && z.x < m && z.y > -m && z.y < m) {
    return false;
  }
  return true;
}

inline void AddEdge(int x, int y, double d) {
  if (IntersectSegment(x <= n ? p[x] : q[x - n], y <= n ? p[y] : q[y - n], s, t)) {
    CheckMin(dis[x][y + (n << 1)], d);
    CheckMin(dis[y][x + (n << 1)], d);
    CheckMin(dis[y + (n << 1)][x], d);
    CheckMin(dis[x + (n << 1)][y], d);
  } else {
    CheckMin(dis[x][y], d);
    CheckMin(dis[y][x], d);
    CheckMin(dis[x + (n << 1)][y + (n << 1)], d);
    CheckMin(dis[y + (n << 1)][x + (n << 1)], d);
  }
}

inline void AddEdge(int x, int y, double d, bool f) {
  if (f) {
    CheckMin(dis[x][y + (n << 1)], d);
    CheckMin(dis[y][x + (n << 1)], d);
    CheckMin(dis[y + (n << 1)][x], d);
    CheckMin(dis[x + (n << 1)][y], d);
  } else {
    CheckMin(dis[x][y], d);
    CheckMin(dis[y][x], d);
    CheckMin(dis[x + (n << 1)][y + (n << 1)], d);
    CheckMin(dis[y + (n << 1)][x + (n << 1)], d);
  }
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m), ans = m << 3;
  for (int i = 1; i <= n; ++i) {
    Read(p[i].x), Read(p[i].y), Read(q[i].x), Read(q[i].y);
  }
  r[0] = Point(m, m), r[1] = Point(m, -m), r[2] = Point(-m, -m), r[3] = Point(-m, m);
  for (int i = 0; i < 4; ++i) {
    ++n, p[n] = q[n] = r[i];
  }
  for (int i = 1; i <= n << 2; ++i) {
    for (int j = 1; j <= n << 2; ++j) {
      dis[i][j] = i == j ? 0 : inf;
    }
  }
  for (int i = 1; i <= n; ++i) {
    AddEdge(i, i + n, 0);
    for (int j = 1; j < i; ++j) {
      if (Check(p[i], p[j])) {
        AddEdge(i, j, Dis(p[i], p[j]));
      }
      if (Check(p[i], q[j])) {
        AddEdge(i, j + n, Dis(p[i], q[j]));
      }
      if (Check(q[i], p[j])) {
        AddEdge(i + n, j, Dis(q[i], p[j]));
      }
      if (Check(q[i], q[j])) {
        AddEdge(i + n, j + n, Dis(q[i], q[j]));
      }
      Point tmp;
      tmp = Projection(p[j], q[j], p[i]);
      if (Mid(p[j], q[j], tmp) && Check(p[i], tmp)) {
        AddEdge(i, j, Dis(p[i], tmp), IntersectSegment(p[i], tmp, s, t) ^ IntersectSegment(p[j], tmp, s, t));
        AddEdge(i, j + n, Dis(p[i], tmp), IntersectSegment(p[i], tmp, s, t) ^ IntersectSegment(q[j], tmp, s, t));
      }
      tmp = Projection(p[j], q[j], q[i]);
      if (Mid(p[j], q[j], tmp) && Check(q[i], tmp)) {
        AddEdge(i + n, j, Dis(q[i], tmp), IntersectSegment(q[i], tmp, s, t) ^ IntersectSegment(p[j], tmp, s, t));
        AddEdge(i + n, j + n, Dis(q[i], tmp), IntersectSegment(q[i], tmp, s, t) ^ IntersectSegment(q[j], tmp, s, t));
      }
      swap(i, j);
      tmp = Projection(p[j], q[j], p[i]);
      if (Mid(p[j], q[j], tmp) && Check(p[i], tmp)) {
        AddEdge(i, j, Dis(p[i], tmp), IntersectSegment(p[i], tmp, s, t) ^ IntersectSegment(p[j], tmp, s, t));
        AddEdge(i, j + n, Dis(p[i], tmp), IntersectSegment(p[i], tmp, s, t) ^ IntersectSegment(q[j], tmp, s, t));
      }
      tmp = Projection(p[j], q[j], q[i]);
      if (Mid(p[j], q[j], tmp) && Check(q[i], tmp)) {
        AddEdge(i + n, j, Dis(q[i], tmp), IntersectSegment(q[i], tmp, s, t) ^ IntersectSegment(p[j], tmp, s, t));
        AddEdge(i + n, j + n, Dis(q[i], tmp), IntersectSegment(q[i], tmp, s, t) ^ IntersectSegment(q[j], tmp, s, t));
      }
      swap(i, j);
    }
  }
  for (int k = 1; k <= n << 2; ++k) {
    for (int i = 1; i <= n << 2; ++i) {
      for (int j = 1; j <= n << 2; ++j) {
        CheckMin(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  for (int i = 1; i <= n << 1; ++i) {
    CheckMin(ans, dis[i][i + (n << 1)]);
  }
  printf("%lf\n", ans);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}

Compilation message (stderr)

fences.cpp: In function 'bool Check(Point, Point)':
fences.cpp:136:42: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
     if (IntersectSegment(x, y, r[i], r[i + 1 & 3])) {
                                        ~~^~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49