Submission #892025

#	Time	Username	Problem	Language	Result	Execution time	Memory
892025		MilosMilutinovic	Fence (CEOI08_fence)	C++14	90 / 100	1 ms	348 KiB

fence

#include <bits/stdc++.h>
 
using namespace std;

struct pt {
  int x;
  int y;
};

bool operator == (pt a, pt b) {
  return a.x == b.x && a.y == b.y;
}

bool operator < (pt a, pt b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int orient(pt a, pt b, pt c) {
  int val = (b.y - a.y) * (c.x - b.x) 
          - (b.x - a.x) * (c.y - b.y);
  if (val == 0) {
    return 0;
  }
  return val > 0 ? 1 : 2; // cw, ccw
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pt> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  vector<pt> b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i].x >> b[i].y;
  }
  vector<pt> up;
  vector<pt> down;
  {
    sort(a.begin(), a.end(), [&](pt p, pt q) {
      if (p.x != q.x) {
        return p.x < q.x;
      } else {
        return p.y < q.y;
      }
    });
    for (int i = 0; i < n; i++) {
      while (up.size() >= 2 && orient(up[up.size() - 2], up.back(), a[i]) == 2) {
        up.pop_back();
      }
      up.push_back(a[i]);
    }
  }
  {
    sort(a.begin(), a.end(), [&](pt p, pt q) {
      if (p.x != q.x) {
        return p.x > q.x;
      } else {
        return p.y > q.y; 
      }
    });
    for (int i = 0; i < n; i++) {
      while (down.size() >= 2 && orient(down[down.size() - 2], down.back(), a[i]) == 2) {
        down.pop_back();
      }
      down.push_back(a[i]);
    }
  }
  set<pt> was;
  vector<pt> hull;
  for (pt p : up) {
    if (was.find(p) == was.end()) {
      was.insert(p);
      hull.push_back(p);
    }
  }
  for (pt p : down) {
    if (was.find(p) == was.end()) {
      was.insert(p);
      hull.push_back(p);
    }
  }
  vector<pt> new_b;
  for (int i = 0; i < m; i++) {
    bool ok = true;
    for (int j = 0; j < hull.size(); j++) {
      if (orient(hull[j], hull[(j + 1) % hull.size()], b[i]) != 1) {
        ok = false;
      }
    }
    if (ok) {
      new_b.push_back(b[i]);
    }
  }
  int left = m - (int) new_b.size();
  b = new_b;
  m = (int) b.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) {
        continue;
      }
      bool ok = true;
      for (int k = 0; k < m; k++) {
        if (orient(a[i], a[j], b[k]) != 1) {
          ok = false;
        }
      }
      if (ok) {
        g[i].push_back(j);
      }
    }
  }
  if (m == 0) {
    cout << 0 << '\n';
    return 0;
  }
  const int inf = (int) 1e9;
  int ans = inf;
  for (int s = 0; s < n; s++) {
    vector<int> dist(n, -1);
    dist[s] = 0;
    vector<int> que(1, s);
    int mn = inf;
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        if (dist[j] == -1) {
          dist[j] = dist[i] + 1;
          que.push_back(j);
        } else if (j == s) {
          mn = min(mn, dist[i] + 1);
        }
      }
    }
    if (mn != inf) {
      ans = min(ans, mn * 20 + left * 111);
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

fence.cpp: In function 'int main()':
fence.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int j = 0; j < hull.size(); j++) {
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10