답안 #44044 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44044	2018-03-29T12:46:42 Z	wxh010910	Fences (JOI18_fences)	C++17	100 / 100	136 ms	2408 KB

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

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.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	728 KB	Output is correct
11	Correct	2 ms	776 KB	Output is correct
12	Correct	2 ms	776 KB	Output is correct
13	Correct	2 ms	776 KB	Output is correct
14	Correct	2 ms	776 KB	Output is correct
15	Correct	2 ms	776 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	2 ms	780 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	808 KB	Output is correct
20	Correct	2 ms	812 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	728 KB	Output is correct
11	Correct	2 ms	776 KB	Output is correct
12	Correct	2 ms	776 KB	Output is correct
13	Correct	2 ms	776 KB	Output is correct
14	Correct	2 ms	776 KB	Output is correct
15	Correct	2 ms	776 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	2 ms	780 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	808 KB	Output is correct
20	Correct	2 ms	812 KB	Output is correct
21	Correct	2 ms	820 KB	Output is correct
22	Correct	2 ms	948 KB	Output is correct
23	Correct	2 ms	952 KB	Output is correct
24	Correct	2 ms	956 KB	Output is correct
25	Correct	2 ms	960 KB	Output is correct
26	Correct	2 ms	964 KB	Output is correct
27	Correct	2 ms	968 KB	Output is correct
28	Correct	2 ms	972 KB	Output is correct
29	Correct	2 ms	976 KB	Output is correct
30	Correct	2 ms	980 KB	Output is correct
31	Correct	2 ms	984 KB	Output is correct
32	Correct	2 ms	988 KB	Output is correct
33	Correct	2 ms	992 KB	Output is correct
34	Correct	2 ms	996 KB	Output is correct
35	Correct	2 ms	1000 KB	Output is correct
36	Correct	2 ms	1004 KB	Output is correct
37	Correct	2 ms	1008 KB	Output is correct
38	Correct	2 ms	1008 KB	Output is correct
39	Correct	2 ms	1016 KB	Output is correct
40	Correct	2 ms	1016 KB	Output is correct
41	Correct	2 ms	1016 KB	Output is correct
42	Correct	2 ms	1016 KB	Output is correct
43	Correct	2 ms	1016 KB	Output is correct

Subtask #3
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	728 KB	Output is correct
11	Correct	2 ms	776 KB	Output is correct
12	Correct	2 ms	776 KB	Output is correct
13	Correct	2 ms	776 KB	Output is correct
14	Correct	2 ms	776 KB	Output is correct
15	Correct	2 ms	776 KB	Output is correct
16	Correct	2 ms	780 KB	Output is correct
17	Correct	2 ms	780 KB	Output is correct
18	Correct	2 ms	784 KB	Output is correct
19	Correct	2 ms	808 KB	Output is correct
20	Correct	2 ms	812 KB	Output is correct
21	Correct	2 ms	820 KB	Output is correct
22	Correct	2 ms	948 KB	Output is correct
23	Correct	2 ms	952 KB	Output is correct
24	Correct	2 ms	956 KB	Output is correct
25	Correct	2 ms	960 KB	Output is correct
26	Correct	2 ms	964 KB	Output is correct
27	Correct	2 ms	968 KB	Output is correct
28	Correct	2 ms	972 KB	Output is correct
29	Correct	2 ms	976 KB	Output is correct
30	Correct	2 ms	980 KB	Output is correct
31	Correct	2 ms	984 KB	Output is correct
32	Correct	2 ms	988 KB	Output is correct
33	Correct	2 ms	992 KB	Output is correct
34	Correct	2 ms	996 KB	Output is correct
35	Correct	2 ms	1000 KB	Output is correct
36	Correct	2 ms	1004 KB	Output is correct
37	Correct	2 ms	1008 KB	Output is correct
38	Correct	2 ms	1008 KB	Output is correct
39	Correct	2 ms	1016 KB	Output is correct
40	Correct	2 ms	1016 KB	Output is correct
41	Correct	2 ms	1016 KB	Output is correct
42	Correct	2 ms	1016 KB	Output is correct
43	Correct	2 ms	1016 KB	Output is correct
44	Correct	107 ms	2316 KB	Output is correct
45	Correct	103 ms	2320 KB	Output is correct
46	Correct	97 ms	2320 KB	Output is correct
47	Correct	98 ms	2408 KB	Output is correct
48	Correct	102 ms	2408 KB	Output is correct
49	Correct	101 ms	2408 KB	Output is correct
50	Correct	136 ms	2408 KB	Output is correct
51	Correct	99 ms	2408 KB	Output is correct
52	Correct	104 ms	2408 KB	Output is correct
53	Correct	105 ms	2408 KB	Output is correct
54	Correct	97 ms	2408 KB	Output is correct
55	Correct	112 ms	2408 KB	Output is correct
56	Correct	102 ms	2408 KB	Output is correct
57	Correct	100 ms	2408 KB	Output is correct
58	Correct	97 ms	2408 KB	Output is correct
59	Correct	99 ms	2408 KB	Output is correct
60	Correct	110 ms	2408 KB	Output is correct
61	Correct	109 ms	2408 KB	Output is correct
62	Correct	2 ms	2408 KB	Output is correct
63	Correct	2 ms	2408 KB	Output is correct
64	Correct	106 ms	2408 KB	Output is correct
65	Correct	113 ms	2408 KB	Output is correct
66	Correct	97 ms	2408 KB	Output is correct
67	Correct	92 ms	2408 KB	Output is correct
68	Correct	89 ms	2408 KB	Output is correct
69	Correct	97 ms	2408 KB	Output is correct
70	Correct	84 ms	2408 KB	Output is correct
71	Correct	93 ms	2408 KB	Output is correct
72	Correct	89 ms	2408 KB	Output is correct

답안 #44044

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 33.0 / 33.0

Subtask #3 49.0 / 49.0

Subtask #1
18.0 / 18.0

Subtask #2
33.0 / 33.0

Subtask #3
49.0 / 49.0