Submission #220597

#	Time	Username	Problem	Language	Result	Execution time	Memory
220597		rama_pang	Fences (JOI18_fences)	C++14	100 / 100	32 ms	4100 KiB

fences

#include <bits/stdc++.h>
using namespace std;
using type_t = double;
const type_t EPS = 1e-9;

struct Point {
  type_t x, y;
  Point() {}
  Point(type_t a, type_t b) : x(a), y(b) {}

  Point operator + (const Point &o) const {
    return Point(x + o.x, y + o.y);
  }

  Point operator - (const Point &o) const {
    return Point(x - o.x, y - o.y);
  }

  friend ostream& operator << (ostream &stream, const Point &p) {
    stream << "(" << p.x << ", " << p.y << ")";
  }
};

struct Line {
  Point a, b;
  Line() {}
  Line(Point a, Point b) : a(a), b(b) {}

  friend ostream& operator << (ostream &stream, const Line &l) {
    stream << "(" << l.a << ", " << l.b << ")";
  }
};

bool Clockwise(Point a, Point b, Point c) { // cross product of vector ab and ac
  Point v1 = b - a, v2 = c - a;
  return (v1.x * v2.y - v1.y * v2.x) > 0;
}

bool CounterClockwise(Point a, Point b, Point c) { // cross product of vector ab and ac
  Point v1 = b - a, v2 = c - a;
  return (v1.x * v2.y - v1.y * v2.x) < 0;
}

bool IntersectLine(Line a, Line b, bool IsTouchIntersect) {
  bool o1 = false, o2 = false;
  o1 |= Clockwise(a.a, a.b, b.a) && CounterClockwise(a.a, a.b, b.b);
  o1 |= CounterClockwise(a.a, a.b, b.a) && Clockwise(a.a, a.b, b.b);
  
  o2 |= Clockwise(b.a, b.b, a.a) && CounterClockwise(b.a, b.b, a.b);
  o2 |= CounterClockwise(b.a, b.b, a.a) && Clockwise(b.a, b.b, a.b);
  
  if (IsTouchIntersect) {
    o1 |= Clockwise(a.a, a.b, b.a) && !Clockwise(a.a, a.b, b.b);
    o1 |= !Clockwise(a.a, a.b, b.a) && Clockwise(a.a, a.b, b.b);
    o2 |= Clockwise(b.a, b.b, a.a) && !Clockwise(b.a, b.b, a.b);
    o2 |= !Clockwise(b.a, b.b, a.a) && Clockwise(b.a, b.b, a.b);
  }

  return o1 && o2;
}

Line PointPointDistance(Point p, Point q) {
  return Line(p, q);
}

Line PointLineDistance(Point p, Line l) {
  Point a = l.a, b = l.b;
  Point vl = b - a;
  Point vp = p - a;

  type_t dot = (vl.x * vp.x + vl.y * vp.y);
  type_t sqr = vl.x * vl.x + vl.y * vl.y;
  type_t partial = dot / sqr;
  
  if (partial > 1 || partial < 0 || sqr == 0) {
    Point d1 = p - l.a;
    Point d2 = p - l.b;
    if (d1.x * d1.x + d1.y * d1.y < d2.x * d2.x + d2.y * d2.y) {
      return PointPointDistance(l.a, p);
    } else {
      return PointPointDistance(l.b, p);
    }
  }

  vl.x *= partial;
  vl.y *= partial;

  return PointPointDistance(vl + a, p);
}

int N, S;
vector<Line> L;
const Line HALFLINE = Line(Point(0, 0), Point(1, 400));

bool IntersectSquare(Line line) {
  bool res = false;
  res |= IntersectLine(line, Line(Point(S, S), Point(-S, S)), false); // top side
  res |= IntersectLine(line, Line(Point(S, S), Point(S, -S)), false); // right side
  res |= IntersectLine(line, Line(Point(-S, -S), Point(-S, S)), false); // left side
  res |= IntersectLine(line, Line(Point(-S, -S), Point(S, -S)), false); // bottom side
  res |= IntersectLine(line, Line(Point(-S, S), Point(S, -S)), false); // diagonal 1
  res |= IntersectLine(line, Line(Point(S, S), Point(-S, -S)), false); // diagonal 2
  return res;
}

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> S;

  for (int i = 0; i < N; i++) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    L.emplace_back(Point(A, B), Point(C, D));
  }

  // Square Corners
  L.emplace_back(Point(S, S), Point(S, S));
  L.emplace_back(Point(S, -S), Point(S, -S));
  L.emplace_back(Point(-S, -S), Point(-S, -S));
  L.emplace_back(Point(-S, S), Point(-S, S)); 
}

struct Edge {
  int u, v;
  Line l;
  bool CrossLine;
  type_t Distance;
  Edge() {}
  Edge(int u, int v, Line l) : u(u), v(v), l(l) {}
};

vector<Edge> edges;

void AddEdge(int u, int v) {
  if (!IntersectSquare(PointPointDistance(L[u].a, L[v].a))) {
    edges.emplace_back(u, v, PointPointDistance(L[u].a, L[v].a));
  }
  if (!IntersectSquare(PointPointDistance(L[u].a, L[v].b))) {
    edges.emplace_back(u, v, PointPointDistance(L[u].a, L[v].b));
  }
  if (!IntersectSquare(PointPointDistance(L[u].b, L[v].a))) {
    edges.emplace_back(u, v, PointPointDistance(L[u].b, L[v].a));
  }
  if (!IntersectSquare(PointPointDistance(L[u].b, L[v].b))) {
    edges.emplace_back(u, v, PointPointDistance(L[u].b, L[v].b));
  }

  if (!IntersectSquare(PointLineDistance(L[u].a, L[v]))) {
    edges.emplace_back(u, v, PointLineDistance(L[u].a, L[v]));
  }
  if (!IntersectSquare(PointLineDistance(L[u].b, L[v]))) {
    edges.emplace_back(u, v, PointLineDistance(L[u].b, L[v]));
  }
  if (!IntersectSquare(PointLineDistance(L[v].a, L[u]))) {
    edges.emplace_back(u, v, PointLineDistance(L[v].a, L[u]));
  }
  if (!IntersectSquare(PointLineDistance(L[v].b, L[u]))) {
    edges.emplace_back(u, v, PointLineDistance(L[v].b, L[u]));
  }
} 

void BuildGraph() {
  int n = L.size();

  { // Split segments that intersecti with HALFLINE into 2 so there are no segments that intersect with HALFLINE
    vector<Line> newL;
    for (int i = 0; i < n; i++) {
      if (IntersectLine(L[i], HALFLINE, true)) { 
        Point Vector = L[i].b - L[i].a;
        type_t l = 0, r = 1;
        for (int it = 0; it < 30; it++) {
          type_t m = (l + r) / 2;
          Point mp = L[i].a + Point(Vector.x * m, Vector.y * m);
          Line p = Line(L[i].a, mp);
          if (IntersectLine(p, HALFLINE, true)) {
            r = m;
          } else {
            l = m;
          }
        }
        Point m;
        m = L[i].a + Point(Vector.x * (r - EPS), Vector.y * (r - EPS));
        newL.emplace_back(L[i].a, m);
        m = L[i].a + Point(Vector.x * (r + EPS), Vector.y * (r + EPS));
        newL.emplace_back(m, L[i].b);
      } else {
        newL.emplace_back(L[i]);
      }
    }
    L = newL;
  }

  n = L.size();

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      AddEdge(i, j);
    }
  }

  for (auto &e : edges) {
    e.Distance = sqrt((e.l.a.x - e.l.b.x) * (e.l.a.x - e.l.b.x) + (e.l.a.y - e.l.b.y) * (e.l.a.y - e.l.b.y));
    e.CrossLine = IntersectLine(e.l, HALFLINE, true);
  }
}

type_t Solve() {
  int n = L.size();
  vector<vector<type_t>> dist(n * 2, vector<type_t>(n * 2, 1e9));

  for (auto &e : edges) {
    if (e.CrossLine) {
      dist[e.u][e.v + n] = min(dist[e.u][e.v + n], e.Distance);
      dist[e.u + n][e.v] = min(dist[e.u + n][e.v], e.Distance);
      dist[e.v][e.u + n] = min(dist[e.v][e.u + n], e.Distance);
      dist[e.v + n][e.u] = min(dist[e.v + n][e.u], e.Distance);
    } else {
      dist[e.u][e.v] = min(dist[e.u][e.v], e.Distance);
      dist[e.u + n][e.v + n] = min(dist[e.u + n][e.v + n], e.Distance);
      dist[e.v][e.u] = min(dist[e.v][e.u], e.Distance);
      dist[e.v + n][e.u + n] = min(dist[e.v + n][e.u + n], e.Distance);
    } 
  }
  
  for (int i = 0; i < 2 * n; i++) {
    dist[i][i] = 0;
  }

  for (int k = 0; k < 2 * n; k++) {
    for (int i = 0; i < 2 * n; i++) {
      for (int j = 0; j < 2 * n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  type_t cycle = 1e9;
  for (int i = 0; i < n; i++) {
    cycle = min(cycle, dist[i][i + n]);
  }

  return cycle;
}

int main() {
  Read();
  BuildGraph();
  cout << fixed << setprecision(10) << Solve() << "\n";
  return 0;
}

Compilation message (stderr)

fences.cpp: In function 'std::ostream& operator<<(std::ostream&, const Point&)':
fences.cpp:21:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^
fences.cpp: In function 'std::ostream& operator<<(std::ostream&, const Line&)':
fences.cpp:31:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^

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