Hashiryo's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/aoj/0284.test.cpp
- View this file on GitHub
- Last update: 2024-09-28 19:54:09+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0284
Depends on
int から long long などのテンプレート (src/Internal/long_traits.hpp)Code
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0284
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include "src/Geometry/Point.hpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
using namespace geo;
int N;
cin >> N;
vector<Point<int>> ps(N);
for (int i= 0; i < N; ++i) cin >> ps[i];
int ord[N];
iota(ord, ord + N, 0), sort(ord, ord + N, [&](int i, int j) { return ps[i] < ps[j]; });
static constexpr int INF= 5e8;
int dp[N + 1][N][N][N], pre[N + 1][N][N][N];
for (int k= 2; k <= N; ++k)
for (int i= N; i--;)
for (int j= N; j--;)
for (int l= N; l--;) dp[k][i][j][l]= INF;
for (int i= N; i--;)
for (int j= i; j--;) dp[2][i][i][j]= 0;
for (int k= 3; k <= N; ++k)
for (int i= N; i--;) {
auto o= ps[ord[i]];
for (int j= 0; j <= i; ++j) {
auto p= ps[ord[j]];
for (int l= i; l--;) {
if (j == l) continue;
if (dp[k - 1][i][j][l] == INF) continue;
auto q= ps[ord[l]];
for (int m= i; m--;) {
if (j == m || l == m) continue;
auto r= ps[ord[m]];
if (ccw(p, q, r) != COUNTER_CLOCKWISE) continue;
if (ccw(q, r, o) != COUNTER_CLOCKWISE) continue;
int a= cross(r - q, o - q) + dp[k - 1][i][j][l];
if (dp[k][i][l][m] > a) dp[k][i][l][m]= a, pre[k][i][l][m]= j;
}
}
}
}
int Q;
cin >> Q;
while (Q--) {
int k;
cin >> k;
int mn= INF, ii= -1, jj= -1, ll= -1;
for (int i= N; i--;)
for (int j= i; j--;)
for (int l= i; l--;)
if (mn > dp[k][i][j][l]) mn= dp[k][i][j][l], ii= i, jj= j, ll= l;
if (ii == -1) {
cout << "NA" << '\n';
continue;
}
vector<int> ch;
for (int kk= k; kk >= 3; --kk) {
ch.push_back(ord[ll]);
int p= pre[kk][ii][jj][ll];
ll= jj, jj= p;
}
ch.push_back(ord[ll]), ch.push_back(ord[ii]);
reverse(ch.begin(), ch.end());
int st= 0;
for (int i= 0; i < k; ++i)
if (auto p= ps[ch[st]], q= ps[ch[i]]; p.y > q.y || (p.y == q.y && p.x > q.x)) st= i;
for (int i= 0; i < k; ++i) cout << ch[(i + st) % k] + 1 << " \n"[i + 1 == k];
}
return 0;
}#line 1 "test/aoj/0284.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0284
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#line 3 "src/Geometry/Point.hpp"
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#line 2 "src/Internal/long_traits.hpp"
// clang-format off
template<class T>struct make_long{using type= T;};
template<>struct make_long<char>{using type= short;};
template<>struct make_long<unsigned char>{using type= unsigned short;};
template<>struct make_long<short>{using type= int;};
template<>struct make_long<unsigned short>{using type= unsigned;};
template<>struct make_long<int>{using type= long long;};
template<>struct make_long<unsigned>{using type= unsigned long long;};
template<>struct make_long<long long>{using type= __int128_t;};
template<>struct make_long<unsigned long long>{using type= __uint128_t;};
template<>struct make_long<float>{using type= double;};
template<>struct make_long<double>{using type= long double;};
template<class T> using make_long_t= typename make_long<T>::type;
// clang-format on
#line 8 "src/Geometry/Point.hpp"
namespace geo {
using namespace std;
struct Visualizer {
ofstream ofs;
Visualizer(string s= "visualize.txt"): ofs(s) { ofs << fixed << setprecision(10); }
friend Visualizer &operator<<(Visualizer &vis, const string &s) { return vis.ofs << s, vis; }
};
template <class K> int sgn(K x) {
if constexpr (is_floating_point_v<K>) {
static constexpr K EPS= 1e-9;
return x < -EPS ? -1 : x > EPS;
} else return x < 0 ? -1 : x > 0;
}
template <class K> K err_floor(K x) {
K y= floor(x);
if constexpr (is_floating_point_v<K>)
if (K z= y + 1, w= x - z; 0 <= sgn(w) && sgn(w - 1) < 0) return z;
return y;
}
template <class K> K err_ceil(K x) {
K y= ceil(x);
if constexpr (is_floating_point_v<K>)
if (K z= y - 1, w= x - z; 0 < sgn(w + 1) && sgn(w) <= 0) return z;
return y;
}
template <class K> struct Point {
K x, y;
Point(K x= K(), K y= K()): x(x), y(y) {}
Point &operator+=(const Point &p) { return x+= p.x, y+= p.y, *this; }
Point &operator-=(const Point &p) { return x-= p.x, y-= p.y, *this; }
Point &operator*=(K a) { return x*= a, y*= a, *this; }
Point &operator/=(K a) { return x/= a, y/= a, *this; }
Point operator+(const Point &p) const { return {x + p.x, y + p.y}; }
Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
Point operator*(K a) const { return {x * a, y * a}; }
Point operator/(K a) const { return {x / a, y / a}; }
friend Point operator*(K a, const Point &p) { return {a * p.x, a * p.y}; }
Point operator-() const { return {-x, -y}; }
bool operator<(const Point &p) const {
int s= sgn(x - p.x);
return s ? s < 0 : sgn(y - p.y) < 0;
}
bool operator>(const Point &p) const { return p < *this; }
bool operator<=(const Point &p) const { return !(p < *this); }
bool operator>=(const Point &p) const { return !(*this < p); }
bool operator==(const Point &p) const { return !sgn(x - p.x) && !sgn(y - p.y); }
bool operator!=(const Point &p) const { return sgn(x - p.x) || sgn(y - p.y); }
Point operator!() const { return {-y, x}; } // rotate 90 degree
friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
friend ostream &operator<<(ostream &os, const Point &p) { return os << "(" << p.x << ", " << p.y << ")"; }
friend Visualizer &operator<<(Visualizer &vis, const Point &p) { return vis.ofs << p.x << " " << p.y << "\n", vis; }
};
template <class K> make_long_t<K> dot(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.x + make_long_t<K>(p.y) * q.y; }
// left turn: > 0, right turn: < 0
template <class K> make_long_t<K> cross(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.y - make_long_t<K>(p.y) * q.x; }
template <class K> make_long_t<K> norm2(const Point<K> &p) { return dot(p, p); }
template <class K> long double norm(const Point<K> &p) { return sqrt(norm2(p)); }
template <class K> make_long_t<K> dist2(const Point<K> &p, const Point<K> &q) { return norm2(p - q); }
template <class T, class U> long double dist(const T &a, const U &b) { return sqrt(dist2(a, b)); }
enum CCW { COUNTER_CLOCKWISE, CLOCKWISE, ONLINE_BACK, ONLINE_FRONT, ON_SEGMENT };
ostream &operator<<(ostream &os, CCW c) { return os << (c == COUNTER_CLOCKWISE ? "COUNTER_CLOCKWISE" : c == CLOCKWISE ? "CLOCKWISE" : c == ONLINE_BACK ? "ONLINE_BACK" : c == ONLINE_FRONT ? "ONLINE_FRONT" : "ON_SEGMENT"); }
template <class K> CCW ccw(const Point<K> &p0, const Point<K> &p1, const Point<K> &p2) {
Point a= p1 - p0, b= p2 - p0;
int s;
if constexpr (is_floating_point_v<K>) s= sgn(sgn(cross(a, b) / sqrt(norm2(a) * norm2(b))));
else s= sgn(cross(a, b));
if (s) return s > 0 ? COUNTER_CLOCKWISE : CLOCKWISE;
if (K d= dot(a, b); sgn(d) < 0) return ONLINE_BACK;
else return sgn(d - norm2(a)) > 0 ? ONLINE_FRONT : ON_SEGMENT;
}
template <class K> struct Line;
template <class K> struct Segment;
template <class K> class Polygon;
template <class K> struct Convex;
template <class K> struct Affine {
K a00= 1, a01= 0, a10= 0, a11= 1;
Point<K> b;
Point<K> operator()(const Point<K> &p) const { return {a00 * p.x + a01 * p.y + b.x, a10 * p.x + a11 * p.y + b.y}; }
Line<K> operator()(const Line<K> &l);
Segment<K> operator()(const Segment<K> &s);
Polygon<K> operator()(const Polygon<K> &p);
Convex<K> operator()(const Convex<K> &c);
Affine operator*(const Affine &r) const { return {a00 * r.a00 + a01 * r.a10, a00 * r.a01 + a01 * r.a11, a10 * r.a00 + a11 * r.a10, a10 * r.a01 + a11 * r.a11, (*this)(r)}; }
Affine &operator*=(const Affine &r) { return *this= *this * r; }
};
template <class K> Affine<K> translate(const Point<K> &p) { return {1, 0, 0, 1, p}; }
}
#line 9 "test/aoj/0284.test.cpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
using namespace geo;
int N;
cin >> N;
vector<Point<int>> ps(N);
for (int i= 0; i < N; ++i) cin >> ps[i];
int ord[N];
iota(ord, ord + N, 0), sort(ord, ord + N, [&](int i, int j) { return ps[i] < ps[j]; });
static constexpr int INF= 5e8;
int dp[N + 1][N][N][N], pre[N + 1][N][N][N];
for (int k= 2; k <= N; ++k)
for (int i= N; i--;)
for (int j= N; j--;)
for (int l= N; l--;) dp[k][i][j][l]= INF;
for (int i= N; i--;)
for (int j= i; j--;) dp[2][i][i][j]= 0;
for (int k= 3; k <= N; ++k)
for (int i= N; i--;) {
auto o= ps[ord[i]];
for (int j= 0; j <= i; ++j) {
auto p= ps[ord[j]];
for (int l= i; l--;) {
if (j == l) continue;
if (dp[k - 1][i][j][l] == INF) continue;
auto q= ps[ord[l]];
for (int m= i; m--;) {
if (j == m || l == m) continue;
auto r= ps[ord[m]];
if (ccw(p, q, r) != COUNTER_CLOCKWISE) continue;
if (ccw(q, r, o) != COUNTER_CLOCKWISE) continue;
int a= cross(r - q, o - q) + dp[k - 1][i][j][l];
if (dp[k][i][l][m] > a) dp[k][i][l][m]= a, pre[k][i][l][m]= j;
}
}
}
}
int Q;
cin >> Q;
while (Q--) {
int k;
cin >> k;
int mn= INF, ii= -1, jj= -1, ll= -1;
for (int i= N; i--;)
for (int j= i; j--;)
for (int l= i; l--;)
if (mn > dp[k][i][j][l]) mn= dp[k][i][j][l], ii= i, jj= j, ll= l;
if (ii == -1) {
cout << "NA" << '\n';
continue;
}
vector<int> ch;
for (int kk= k; kk >= 3; --kk) {
ch.push_back(ord[ll]);
int p= pre[kk][ii][jj][ll];
ll= jj, jj= p;
}
ch.push_back(ord[ll]), ch.push_back(ord[ii]);
reverse(ch.begin(), ch.end());
int st= 0;
for (int i= 0; i < k; ++i)
if (auto p= ps[ch[st]], q= ps[ch[i]]; p.y > q.y || (p.y == q.y && p.x > q.x)) st= i;
for (int i= 0; i < k; ++i) cout << ch[(i + st) % k] + 1 << " \n"[i + 1 == k];
}
return 0;
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++-13 | 00_sample_00.in |
AC |
5 ms | 4 MB |
| g++-13 | 00_sample_01.in |
AC |
4 ms | 4 MB |
| g++-13 | 01_midium_00.in |
AC |
4 ms | 4 MB |
| g++-13 | 01_midium_01.in |
AC |
4 ms | 4 MB |
| g++-13 | 01_midium_02.in |
AC |
5 ms | 4 MB |
| g++-13 | 02_critical_00.in |
AC |
10 ms | 10 MB |
| g++-13 | 02_critical_01.in |
AC |
10 ms | 10 MB |
| g++-13 | 03_random_00.in |
AC |
23 ms | 22 MB |
| g++-13 | 04_maximum_00.in |
AC |
25 ms | 24 MB |
| clang++-18 | 00_sample_00.in |
AC |
5 ms | 4 MB |
| clang++-18 | 00_sample_01.in |
AC |
4 ms | 4 MB |
| clang++-18 | 01_midium_00.in |
AC |
4 ms | 4 MB |
| clang++-18 | 01_midium_01.in |
AC |
4 ms | 4 MB |
| clang++-18 | 01_midium_02.in |
AC |
4 ms | 4 MB |
| clang++-18 | 02_critical_00.in |
AC |
8 ms | 9 MB |
| clang++-18 | 02_critical_01.in |
AC |
9 ms | 10 MB |
| clang++-18 | 03_random_00.in |
AC |
13 ms | 17 MB |
| clang++-18 | 04_maximum_00.in |
AC |
13 ms | 18 MB |