Submission #64985214

---

Source Code Expand

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <atcoder/dsu>
#include <atcoder/segtree>
// #include <atcoder/mincostflow>

#define FINAL_SUBMIT 0

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

#if FINAL_SUBMIT
#define HHH(x)
#define LOG(x)
#define GRAPH(x, y)
#define CERR() if (false) std::cerr
#define NDEBUG
#else
#define HHH(x) std::cerr << "L" << __LINE__ << ": " << #x << " : " << (x) << "\n"
#define LOG(x) std::cerr << #x << " = " << x << "\n"
#define GRAPH(x, y) std::cerr << "graph " << x << " " << y << "\n"
#define CERR() std::cerr
#endif

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

using ll = long long;
using ld = double;
using P = std::pair<int, int>;
constexpr int INF = 1e9;
constexpr double PI = acos(-1.0);

// Template for printing pair and vector
std::ostream& operator<<(std::ostream& os, const P& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  os << "[";
  for (const T& e : vec) os << " " << e;
  os << " ]";
  return os;
}

class Timer {
public:
  // static constexpr double time_limit = 1.98;
  static constexpr int64_t CYCLES_PER_SEC = 2900000000;
  // static constexpr double CYCLES = CYCLES_PER_SEC * time_limit;
  int64_t start, stop;
#if 0
  // Deterministic mode
  inline int64_t get_cycle() const {
    static int64_t cycle = 0;
    return cycle += 30000;
  }
#else
  inline int64_t get_cycle() const {
    uint32_t low, high;
    __asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
    return int64_t(low) | (int64_t(high) << 32);
  }
#endif
  Timer(double time_limit) : start(get_cycle()), stop(start + CYCLES_PER_SEC * time_limit) {}
  inline void reset_stop(double time_limit) { stop = start + CYCLES_PER_SEC *  time_limit; }
  inline bool within(int64_t end) const { return get_cycle() < end; }
  inline bool within() const { return within(stop); }
  inline double elapsed() const { return (get_cycle() - start) / double(CYCLES_PER_SEC); }
};

class XorShift {
  unsigned int x, y, z, w;
public:
  XorShift() : x(314159265), y(358979323), z(846264338), w(327950288) {}
  inline unsigned int next() {
    unsigned int t = x ^ x << 11;
    x = y; y = z; z = w;
    return w = w ^ w >> 19 ^ t ^ t >> 8;
  }
  inline int next(int n) { return next() % n; }
  inline int next(size_t n) { return next() % n; }
  inline int next(int lo, int hi) { return lo + next(hi - lo + 1); }
  inline double next(double x) { return double(next()) / (1LL << 32) * x; }
};

double get_param(const char* env_var) {
  char* ret = getenv(env_var);
  assert (ret != nullptr);
  return stod(std::string(ret));
}

// double a_param = get_param("A_PARAM");
// double b_param = get_param("B_PARAM");
// double c_param = get_param("C_PARAM");
// int a_param = get_param("A_PARAM");
// int j_param = get_param("J_PARAM");

Timer timer(1.95);
XorShift rnd;

class SimulatedAnnealing {
public:
  constexpr static int LOG_SIZE = 0x10000;
  constexpr static int UPDATE_INTERVAL = 0xFF;
  constexpr static double START_TEMP = 10000;
  constexpr static double END_TEMP = 300;
  constexpr static int64_t CYCLES = Timer::CYCLES_PER_SEC * 0.47;
  // constexpr static double TEMP_RATIO = (END_TEMP - START_TEMP) / CYCLES;  // linear
  constexpr static double TEMP_RATIO = log(END_TEMP / START_TEMP) / CYCLES;  // exponential
  double logp[LOG_SIZE];
  long long iteration = 0;
  int64_t cycle = 0;
  int64_t start = timer.get_cycle();
  // int64_t stop = timer.stop;
  int64_t stop = start + CYCLES;
  bool record = false;
  double temp = START_TEMP;

  SimulatedAnnealing() {
    constexpr double inv = 1.0 / LOG_SIZE;
    REP(i,LOG_SIZE) logp[i] = log((i + 0.5) * inv);
    std::mt19937 rng;
    std::shuffle(logp, logp + LOG_SIZE, rng);
  }

  inline bool End() {
    iteration++;
    // if ((iteration & UPDATE_INTERVAL) != 0) return false;
    cycle = timer.get_cycle();
    // temp = END_TEMP - (stop - cycle) * TEMP_RATIO;  // linear
    temp = START_TEMP * exp((cycle - start) * TEMP_RATIO);  // exponential
    return cycle >= stop;
  }

  inline bool Accept(double diff) {
    static unsigned short index = 0;
    return diff >= 0 || diff > logp[index++] * temp;
  }
};

using namespace std;

double sq(double x) { return x * x; }

using Point = pair<ll, ll>;
int nA, nB, nC;
Point A[128], B[128], C[128];

int Orient(Point a, Point b, Point p) {
  // return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
  return (b.first - a.first) * (p.second - a.second) - (b.second - a.second) * (p.first - a.first);
}

bool Contains(Point p, Point a, Point b, Point c) {
  // # degenerate (colinear) case
  // if orient(a, b, c) == 0:
  //     if orient(a, b, p) != 0 or orient(a, c, p) != 0:
  //         return False
  //     xs = (a[0], b[0], c[0])
  //     ys = (a[1], b[1], c[1])
  //     return min(xs) <= p[0] <= max(xs) and min(ys) <= p[1] <= max(ys)

  // # non‐degenerate: check same side of all edges
  // c1 = orient(a, b, p)
  // c2 = orient(b, c, p)
  // c3 = orient(c, a, p)
  // return (c1 >= 0 and c2 >= 0 and c3 >= 0) or (c1 <= 0 and c2 <= 0 and c3 <= 0)
  if (Orient(a, b, c) == 0) {
    if (Orient(a, b, p) != 0 || Orient(a, c, p) != 0) return false;
    auto xs = array<ll, 3>{a.first, b.first, c.first};
    auto ys = array<ll, 3>{a.second, b.second, c.second};
    return min({xs[0], xs[1], xs[2]}) <= p.first && p.first <= max({xs[0], xs[1], xs[2]}) &&
           min({ys[0], ys[1], ys[2]}) <= p.second && p.second <= max({ys[0], ys[1], ys[2]});
  }
  int c1 = Orient(a, b, p);
  int c2 = Orient(b, c, p);
  int c3 = Orient(c, a, p);
  return (c1 >= 0 && c2 >= 0 && c3 >= 0) || (c1 <= 0 && c2 <= 0 && c3 <= 0);
}

void SetUp() {
  scanf("%d%d%d", &nA, &nB, &nC);
  REP(i, nA) scanf("%lld%lld", &A[i].first, &A[i].second);
  REP(i, nB) scanf("%lld%lld", &B[i].first, &B[i].second);
  REP(i, nC) scanf("%lld%lld", &C[i].first, &C[i].second);
}

// vector<pair<Point, Point>> Solve(const vector<Point> &ok, const vector<Point> &ng) {
//   vector<bool> used(ok.size(), false);
//   int l = rnd.next(0, ok.size() - 1);
//   int r = l;
//   cerr << "l = " << l << " r = " << r << endl;
//   vector<pair<Point, Point>> res;
//   res.emplace_back(ok[l], ok[r]);
//   used[l] = true;
//   used[r] = true;
//   for (;;) {
//     int best = -1;
//     double best_dist = 1e30;
//     vector<int> best_count;
//     REP(i,ok.size()) {
//       if (used[i]) continue;
//       double dist = sq(ok[l].first - ok[i].first) + sq(ok[l].second - ok[i].second);
//       if (dist >= best_dist) continue;
//       bool flag = true;
//       for (auto &p : ng) {
//         if (Contains(p, ok[l], ok[i], ok[r])) {
//           flag = false;
//           break;
//         }
//       }
//       cerr << i << " " << dist << " " << flag << endl;
//       if (!flag) continue;
//       vector<int> count;
//       REP(j,ok.size()) {
//         if (used[j]) continue;
//         if (Contains(ok[j], ok[l], ok[i], ok[r])) {
//           count.push_back(j);
//         }
//       }
//       if (count.empty()) continue;
//       dist /= int(count.size());
//       cerr << i <<  " " << count.size() << endl;
//       if (dist < best_dist) {
//         best = i;
//         best_count = count;
//         best_dist = dist;
//       }
//     }
//     cerr << "Left: " << best << " " << best_dist << endl;
//     if (best == -1) break;
//     l = best;
//     for (int i : best_count) {
//       used[i] = true;
//     }

//     best = -1; best_dist = 1e30;
//     REP(i,ok.size()) {
//       if (used[i]) continue;
//       double dist = sq(ok[r].first - ok[i].first) + sq(ok[r].second - ok[i].second);
//       if (dist >= best_dist) continue;
//       bool flag = true;
//       int loop = 0;
//       for (auto &p : ng) {
//         if (Contains(p, ok[l], ok[i], ok[r])) {
//           flag = false;
//           cerr << "NG: " << i << " " << loop << " " << p.first << " " << p.second << endl;
//           break;
//         }
//         ++loop;
//       }
//       cerr << i << " " << dist << " " << flag << endl;
//       if (!flag) continue;
//       vector<int> count;
//       REP(j,ok.size()) {
//         if (used[j]) continue;
//         if (Contains(ok[j], ok[l], ok[i], ok[r])) {
//           count.push_back(j);
//         }
//       }
//       if (count.empty()) continue;
//       dist /= int(count.size());
//       if (dist < best_dist) {
//         best = i;
//         best_count = count;
//         best_dist = dist;
//       }
//     }
//     cerr << "Right: " << best << " " << best_dist << endl;
//     if (best == -1) break;
//     r = best;
//     for (int i : best_count) {
//       used[i] = true;
//     }

//     res.emplace_back(ok[l], ok[r]);
//   }
//   return res;
// }

vector<pair<Point, Point>> SolveA(const vector<Point> &ok, const vector<Point> &ng) {
  int N = ok.size();
  vector<int> perm(N);
  iota(perm.begin(), perm.end(), 0);
  vector<vector<double>> dist(N, vector<double>(N, 0));
  REP(i,N) {
    REP(j,N) {
      dist[i][j] = sqrt(sq(ok[i].first - ok[j].first) + sq(ok[i].second - ok[j].second));
    }
  }
  int iter = 0;
  int accept = 0;
  SimulatedAnnealing sa;
  while (!sa.End()) {
    ++iter;
    int l = rnd.next(0, N - 1);
    int r = rnd.next(0, N - 1);
    if (l > r) swap(l, r);
    if (r - l <= 1) continue;
    double diff = 0;
    if (l > 0) diff -= dist[perm[l - 1]][perm[l]];
    if (r < N - 1) diff -= dist[perm[r - 1]][perm[r]];
    if (l > 0) diff += dist[perm[l - 1]][perm[r - 1]];
    if (r < N - 1) diff += dist[perm[l]][perm[r]];
    if (sa.Accept(-diff)) {
      ++accept;
      reverse(perm.begin() + l, perm.begin() + r);
    }
  }

  vector<pair<Point, Point>> res;
  vector<bool> vl(N, true), vr(N, true);
  auto Compute = [&]() {
    vector<bool> covered(N, false);
    int n_covered = 0;
    int l = 0, r = 0;
    while (l < N && !vl[l]) ++l;
    while (r < N && !vr[l]) ++r;
    double sum = 0;
    for (;;) {
      int nl = l + 1;
      while (nl < N && !vl[nl]) ++nl;
      if (nl == N) {
        if (n_covered != N) return 1e30;
        return sum;
      }
      for (Point p : ng) {
        if (Contains(p, ok[perm[l]], ok[perm[nl]], ok[perm[r]])) {
          return 1e30;
        }
      }
      REP(i,ok.size()) {
        if (covered[i]) continue;
        if (Contains(ok[i], ok[perm[l]], ok[perm[nl]], ok[perm[r]])) {
          covered[i] = true;
          n_covered++;
        }
      }
      double d1 = dist[perm[l]][perm[nl]];
      l = nl;

      int nr = r + 1;
      while (nr < N && !vr[nr]) ++nr;
      assert(nr != N);
      for (Point p : ng) {
        if (Contains(p, ok[perm[l]], ok[perm[nr]], ok[perm[r]])) {
          return 1e30;
        }
      }
      REP(i,ok.size()) {
        if (covered[i]) continue;
        if (Contains(ok[i], ok[perm[l]], ok[perm[nr]], ok[perm[r]])) {
          covered[i] = true;
          n_covered++;
        }
      }
      double d2 = dist[perm[r]][perm[nr]];
      r = nr;
      sum += d1 + d2;
    }
  };
  double best_cost = Compute();
  LOG(best_cost);
  SimulatedAnnealing sa2;
  while (!sa2.End()) {
    ++iter;
    int l = rnd.next(0, N - 1);
    int r = rnd.next(0, N - 1);
    if (vl[l] != vr[r]) continue;
    vl[l] = !vl[l];
    vr[r] = !vr[r];
    double cost = Compute();
    if (sa.Accept(best_cost - cost)) {
      best_cost = cost;
    } else {
      vl[l] = !vl[l];
      vr[r] = !vr[r];
    }
  }
  double final_cost = best_cost;
  LOG(final_cost);

  {
    int countl = 0, countr = 0;
    REP(i,N) {
      if (vl[i]) countl++;
      if (vr[i]) countr++;
    }
    REP(i,N) cerr << vl[i] << " " << vr[i] << endl;
    LOG(countl);
    LOG(countr);
    assert(countl == countr);

    int l = 0, r = 0;
    for (;;) {
      while (l < N && !vl[l]) ++l;
      while (r < N && !vr[r]) ++r;
      assert((l == N) == (r == N));
      if (l == N || r == N) break;
      res.emplace_back(ok[perm[l]], ok[perm[r]]);
      ++l; ++r;
    }
  }
  LOG(iter);
  LOG(accept);
  return res;
}

void Print(const vector<pair<Point, Point>> &res1, const vector<pair<Point, Point>> &res2) {
  int N = max(res1.size(), res2.size());
  LOG(N);
  REP(i,N) {
    int l = min(i, (int)res1.size() - 1);
    int r = min(i, (int)res2.size() - 1);
    cout << res1[l].first.first << " " << res1[l].first.second << " "
         << res1[l].second.first << " " << res1[l].second.second << " "
         << res2[r].first.first << " " << res2[r].first.second << " "
         << res2[r].second.first << " " << res2[r].second.second << "\n";
  }
  fflush(stdout);
}

tuple<int, vector<pair<Point, Point>>, vector<pair<Point, Point>>> SolveBImpl(int rot) {
  vector<pair<int, int>> events1;
  int rot1 = max(rot, 0);
  int rot2 = max(-rot, 0);
  REP(i,nA) {
    int d = rot1 * ((1000000 - A[i].second) + rot2 * A[i].second) / 1000000;
    events1.emplace_back(A[i].first - d, 0);
  }
  REP(i,nB) {
    int d = rot1 * ((1000000 - B[i].second) + rot2 * B[i].second) / 1000000;
    events1.emplace_back(B[i].first - d, 1);
  }
  sort(events1.begin(), events1.end());

  vector<pair<int, int>> events2;
  REP(i,nA) {
    int d = rot1 * ((1000000 - A[i].first) + rot2 * A[i].first) / 1000000;
    events2.emplace_back(A[i].second - d, 0);
  }
  REP(i,nB) {
    int d = rot1 * ((1000000 - B[i].first) + rot2 * B[i].first) / 1000000;
    events2.emplace_back(B[i].second - d, 1);
  }
  sort(events2.begin(), events2.end());

  int dist1 = events1.back().first - events1.front().first;
  int dist2 = events2.back().first - events2.front().first;

  REP(i,nA+nB-1) {
    if (events1[i].first == events1[i + 1].first) dist1 = 1e8;
    if (events1[i].first == 0) dist1 = 1e8;
    if (events2[i].first == events2[i + 1].first) dist2 = 1e8;
    if (events2[i].first == 0) dist2 = 1e8;
  }
  vector<pair<Point, Point>> res0, res1;
  if (dist1 < dist2) {
    int sx = max(events1[0].first - 1, 0);
    res0.emplace_back(Point{sx + rot1, 0}, Point{sx + rot2, 1000000});
    res1.emplace_back(Point{sx + rot1, 0}, Point{sx + rot2, 1000000});
    for (auto [x, type] : events1) {
      if (type == 0) {
        res0.emplace_back(Point{x + rot1, 0}, Point{x + rot2, 1000000});
        res1.emplace_back(Point{x - 1 + rot1, 0}, Point{x - 1 + rot2, 1000000});
      } else {
        res0.emplace_back(Point{x - 1 + rot1, 0}, Point{x - 1 + rot2, 1000000});
        res1.emplace_back(Point{x + rot1, 0}, Point{x + rot2, 1000000});
      }
    }
  } else {
    int sx = max(events2[0].first - 1, 0);
    res0.emplace_back(Point{0, sx + rot1}, Point{1000000, sx + rot2});
    res1.emplace_back(Point{0, sx + rot1}, Point{1000000, sx + rot2});
    for (auto [x, type] : events2) {
      if (type == 0) {
        res0.emplace_back(Point{0, x + rot1}, Point{1000000, x + rot2});
        res1.emplace_back(Point{0, x + rot1 - 1}, Point{1000000, x + rot2 - 1});
      } else {
        res0.emplace_back(Point{0, x + rot1 - 1}, Point{1000000, x + rot2 - 1});
        res1.emplace_back(Point{0, x + rot1}, Point{1000000, x + rot2});
      }
    }
  }
  return {min(dist1, dist2), res0, res1};
}

void SolveB() {
  int min_dist = 1e8;
  vector<pair<Point, Point>> res0, res1;
  std::tie(min_dist, res0, res1) = SolveBImpl(0);
  for (int rot = -9999; rot < 10000; ++rot) {
    // auto [dist, res0_, res1_] = SolveBImpl(rnd.next(-9900, 9900));
    auto [dist, res0_, res1_] = SolveBImpl(rot);
    // cerr << dist << " " << min_dist << endl;
    if (dist < min_dist) {
      min_dist = dist;
      res0 = res0_;
      res1 = res1_;
    }
  }
  LOG(timer.elapsed());
  Print(res0, res1);
}

int main() {
  SetUp();
  vector<Point> ok;
  vector<Point> ng;
  REP(i,nA) ok.push_back(A[i]);
  REP(i,nB) ng.push_back(B[i]);
  REP(i,nC) ng.push_back(C[i]);
  if (nC == 0) {
    SolveB();
    return 0;
  }
  auto res1 = SolveA(ok, ng);
  vector<pair<Point, Point>> res2;
  if (nB == 0) {
    res2.emplace_back(Point{0, 0}, Point{0, 0});
  } else {
    vector<Point> ok2;
    vector<Point> ng2;
    REP(i,nA) ng2.push_back(A[i]);
    REP(i,nB) ok2.push_back(B[i]);
    REP(i,nC) ng2.push_back(C[i]);
    res2 = SolveA(ok2, ng2);
  }

  Print(res1, res2);

  double elapsed = timer.elapsed();
  LOG(elapsed);
  std::_Exit(0);
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void SetUp()’:
Main.cpp:209:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  209 |   scanf("%d%d%d", &nA, &nB, &nC);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:210:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  210 |   REP(i, nA) scanf("%lld%lld", &A[i].first, &A[i].second);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:211:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  211 |   REP(i, nB) scanf("%lld%lld", &B[i].first, &B[i].second);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:212:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  212 |   REP(i, nC) scanf("%lld%lld", &C[i].first, &C[i].second);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result