結果
| 問題 | No.2180 Comprehensive Line Segments |
| コンテスト | |
| ユーザー |
 butsurizuki
|
| 提出日時 | 2026-07-22 12:08:47 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 51 ms / 5,000 ms |
| + 556µs | |
| コード長 | 12,252 bytes |
| 記録 | |
| コンパイル時間 | 4,903 ms |
| コンパイル使用メモリ | 366,080 KB |
| 実行使用メモリ | 27,776 KB |
| 最終ジャッジ日時 | 2026-07-22 12:08:55 |
| 合計ジャッジ時間 | 4,426 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;
using u64 = unsigned long long;
struct Point {
i64 x, y;
Point operator-(const Point& o) const {
return {x - o.x, y - o.y};
}
Point operator-() const {
return {-x, -y};
}
bool operator<(const Point& o) const {
return tie(x, y) < tie(o.x, o.y);
}
bool operator==(const Point& o) const {
return x == o.x && y == o.y;
}
};
i128 cross(const Point& a, const Point& b) {
return (i128)a.x * b.y - (i128)a.y * b.x;
}
i128 dot(const Point& a, const Point& b) {
return (i128)a.x * b.x + (i128)a.y * b.y;
}
Point normalize_dir(Point v) {
i64 g = std::gcd(std::abs(v.x), std::abs(v.y));
v.x /= g;
v.y /= g;
return v;
}
int half_plane(const Point& v) {
return (v.y > 0 || (v.y == 0 && v.x >= 0)) ? 0 : 1;
}
struct PolarLess {
bool operator()(const Point& a, const Point& b) const {
int ha = half_plane(a);
int hb = half_plane(b);
if (ha != hb) return ha < hb;
return cross(a, b) > 0;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<Point> P(N);
for (auto& p : P) cin >> p.x >> p.y;
if (N <= 2) {
cout << 1 << '\n';
return 0;
}
/*
* Input-point pairs determine every direction which can become
* a boundary of a feasible direction interval.
*/
vector<Point> dirs;
dirs.reserve(N * (N - 1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i != j) {
dirs.push_back(normalize_dir(P[j] - P[i]));
}
}
}
sort(dirs.begin(), dirs.end(), PolarLess());
dirs.erase(unique(dirs.begin(), dirs.end()), dirs.end());
const int M = (int)dirs.size();
const int ATOMS = 2 * M;
const int WORDS = (ATOMS + 63) / 64;
// N <= 12 => M <= 132 => ATOMS <= 264.
assert(WORDS <= 5);
map<Point, int> dir_id;
for (int k = 0; k < M; ++k) {
dir_id[dirs[k]] = k;
}
vector<int> opposite(M);
for (int k = 0; k < M; ++k) {
opposite[k] = dir_id[-dirs[k]];
}
vector<vector<int>> direction(N, vector<int>(N, -1));
vector<vector<int>> on_segment(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
direction[i][j] =
dir_id[normalize_dir(P[j] - P[i])];
Point v = P[j] - P[i];
int mask = 0;
for (int k = 0; k < N; ++k) {
Point a = P[k] - P[i];
Point b = P[k] - P[j];
// P[k] lies on the closed segment [P[i],P[j]].
if (cross(v, a) == 0 && dot(a, b) <= 0) {
mask |= 1 << k;
}
}
on_segment[i][j] = mask;
}
}
array<u64, 5> all_atoms{};
for (int w = 0; w < WORDS; ++w) {
all_atoms[w] = ~0ULL;
}
if (ATOMS % 64 != 0) {
all_atoms[WORDS - 1] =
(1ULL << (ATOMS % 64)) - 1;
}
auto set_bit = [&](u64* bits, int pos) {
bits[pos >> 6] |= 1ULL << (pos & 63);
};
auto has_bit = [&](const u64* bits, int pos) -> bool {
return ((bits[pos >> 6] >> (pos & 63)) & 1ULL) != 0;
};
auto low_mask = [](int len) -> u64 {
return len == 64 ? ~0ULL : (1ULL << len) - 1;
};
/*
* Atom 2*k : exact direction dirs[k]
* Atom 2*k + 1 : open interval (dirs[k], dirs[k+1])
*
* left[w,k] = (-dirs[k], dirs[w]]
* right[w,k] = [ dirs[w],-dirs[k])
*
* Intervals are taken counterclockwise.
*/
vector<u64> left((size_t)M * M * WORDS, 0);
vector<u64> right((size_t)M * M * WORDS, 0);
for (int w = 0; w < M; ++w) {
int end = 2 * w;
for (int k = 0; k < M; ++k) {
u64* L =
&left[((size_t)w * M + k) * WORDS];
u64* R =
&right[((size_t)w * M + k) * WORDS];
int begin = 2 * opposite[k];
/*
* This entry is not queried by turn_through, but
* define it harmlessly as the singleton {dirs[w]}.
*/
if (begin == end) {
set_bit(L, end);
set_bit(R, end);
continue;
}
int p = (begin + 1) % ATOMS;
while (true) {
set_bit(L, p);
if (p == end) break;
p = (p + 1) % ATOMS;
}
p = end;
while (p != begin) {
set_bit(R, p);
p = (p + 1) % ATOMS;
}
}
}
/*
* Find the first occupied atom in cyclic forward order,
* looking at exactly len atom positions.
*/
auto find_forward =
[&](const u64* bits, int start, int len) -> int {
while (len > 0) {
if (start >= ATOMS) start = 0;
int word = start >> 6;
int offset = start & 63;
int take =
min({len, 64 - offset, ATOMS - start});
u64 x =
(bits[word] >> offset) & low_mask(take);
if (x != 0) {
return start + __builtin_ctzll(x);
}
start += take;
len -= take;
}
return -1;
};
/*
* Find the first occupied atom in cyclic backward order,
* looking at exactly len atom positions.
*/
auto find_backward =
[&](const u64* bits, int start, int len) -> int {
while (len > 0) {
if (start < 0) start = ATOMS - 1;
int word = start >> 6;
int offset = start & 63;
int take = min(len, offset + 1);
int lo = offset - take + 1;
u64 x =
bits[word] & (low_mask(take) << lo);
if (x != 0) {
return word * 64
+ (63 - __builtin_clzll(x));
}
start -= take;
len -= take;
}
return -1;
};
/*
* A is the previous recorded input point.
* B is the new input point.
* dirs[w] is the direction of B-A.
*
* The old endpoint is A+t*u, t>=0.
* The new segment direction after passing B is parallel to
*
* (B-A)-t*u.
*/
auto turn_through =
[&](const u64* current, int w, u64* result) {
int exact_w = 2 * w;
/*
* If u=w, put the old endpoint exactly at B.
* The new segment can then leave B in any direction.
*/
if (has_bit(current, exact_w)) {
for (int q = 0; q < WORDS; ++q) {
result[q] = all_atoms[q];
}
return;
}
for (int q = 0; q < WORDS; ++q) {
result[q] = 0;
}
// t=0 always gives direction w.
set_bit(result, exact_w);
/*
* Counterclockwise side of w.
* The closest occupied atom produces the largest interval.
*/
int atom = find_forward(
current,
(exact_w + 1) % ATOMS,
M - 1
);
if (atom != -1) {
// Clockwise-side boundary of the atom.
int k = atom / 2;
const u64* add =
&left[((size_t)w * M + k) * WORDS];
for (int q = 0; q < WORDS; ++q) {
result[q] |= add[q];
}
}
/*
* Clockwise side of w.
*/
atom = find_backward(
current,
(exact_w - 1 + ATOMS) % ATOMS,
M - 1
);
if (atom != -1) {
// Counterclockwise-side boundary of the atom.
int k =
(atom % 2 == 0
? atom / 2
: (atom / 2 + 1) % M);
const u64* add =
&right[((size_t)w * M + k) * WORDS];
for (int q = 0; q < WORDS; ++q) {
result[q] |= add[q];
}
}
};
const int FULL = (1 << N) - 1;
/*
* Connecting all input points in any order gives N-1 links.
*/
int answer = N - 1;
/*
* dp[mask][last][links]
* = feasible extension-direction atoms.
*/
const int COSTS = N; // links = 0,...,N-1
vector<u64> dp(
(size_t)(1 << N) * N * COSTS * WORDS,
0
);
auto state =
[&](int mask, int last, int links) -> u64* {
size_t index =
(((size_t)mask * N + last) * COSTS + links)
* WORDS;
return dp.data() + index;
};
/*
* Initialization by the first link.
*/
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
int mask = on_segment[i][j];
if (mask == FULL) {
cout << 1 << '\n';
return 0;
}
set_bit(
state(mask, j, 1),
2 * direction[i][j]
);
}
}
array<u64, 5> seen{};
array<u64, 5> current{};
array<u64, 5> next_directions{};
/*
* Every transition adds an unmasked point.
* Thus increasing numerical mask order is topological.
*/
for (int mask = 0; mask <= FULL; ++mask) {
for (int last = 0; last < N; ++last) {
for (int q = 0; q < WORDS; ++q) {
seen[q] = 0;
}
for (int links = 1;
links < answer;
++links) {
u64* cur = state(mask, last, links);
bool nonempty = false;
/*
* A direction already achievable with fewer links
* dominates the same direction at this cost.
*/
for (int q = 0; q < WORDS; ++q) {
current[q] = cur[q] & ~seen[q];
cur[q] = current[q];
seen[q] |= current[q];
nonempty |= current[q] != 0;
}
if (!nonempty) continue;
for (int next = 0; next < N; ++next) {
if ((mask >> next) & 1) continue;
int w = direction[last][next];
/*
* Continue the current link straight through P[next].
*/
if (has_bit(current.data(), 2 * w)) {
int new_mask =
mask | on_segment[last][next];
if (new_mask == FULL) {
answer = min(answer, links);
} else {
set_bit(
state(new_mask, next, links),
2 * w
);
}
}
/*
* Add one new link and make it pass through P[next].
*/
if (links + 1 < answer) {
turn_through(
current.data(),
w,
next_directions.data()
);
int new_mask = mask | (1 << next);
if (new_mask == FULL) {
answer =
min(answer, links + 1);
} else {
u64* dst =
state(
new_mask,
next,
links + 1
);
for (int q = 0;
q < WORDS;
++q) {
dst[q] |= next_directions[q];
}
}
}
}
}
}
}
cout << answer << '\n';
return 0;
}