SHARE
TWEET

Untitled

a guest Jul 15th, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 4010;
  6.  
  7. struct point {
  8.     int x, y;
  9. };
  10.  
  11. struct line {
  12.     point a, b;
  13. };
  14.  
  15. point p[MAXN];
  16. line l[MAXN];
  17. int dist[MAXN];
  18.  
  19. bool intersect(line l1, line l2, point &ans) {
  20.     point a = l1.a, b = l1.b, c = l2.a, d = l2.b;
  21.     if (a.x == b.x && c.x == d.x) return false;
  22.     if (a.y == b.y && c.y == d.y) return false;
  23.     if (a.y == b.y) {
  24.         if (min(c.y, d.y) > a.y || max(c.y, d.y) < a.y) return false;
  25.         if (min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)) {
  26.             ans.x = c.x;
  27.             ans.y = a.y;
  28.             return true;
  29.         }
  30.     }
  31.     else if (a.x == b.x) {
  32.         if (min(c.x, d.x) > a.x || max(c.x, d.x) < a.x) return false;
  33.         if (min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y)) {
  34.             ans.x = a.x;
  35.             ans.y = c.y;
  36.             return true;
  37.         }
  38.     }
  39.     return false;
  40. }
  41.  
  42. int distance(point p1, point p2) {
  43.     return abs(p1.x - p2.x) + abs(p1.y - p2.y);
  44. }
  45.  
  46. int main() {
  47.     int n;
  48.     cin >> n;
  49.     for (int i = 0; i < n; i++) {
  50.         cin >> p[i].x >> p[i].y;
  51.         if (i) {
  52.             l[i].a = p[i - 1];
  53.             l[i].b = p[i];
  54.             dist[i] = dist[i - 1] + distance(p[i - 1], p[i]);
  55.         }
  56.     }
  57.     int ans = dist[n - 1];
  58.     for (int i = 1; i < n; i++) {
  59.         for (int j = i + 2; j < n; j++) {
  60.             point inter;
  61.             if (intersect(l[i], l[j], inter)) {
  62.                 int res = dist[j] - dist[i - 1];
  63.                 res -= distance(l[j].b, inter);
  64.                 res -= distance(l[i].a, inter);
  65.                 ans = min(ans, res);
  66.             }
  67.         }
  68.     }
  69.     cout << ans << '\n';
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top