結果
| 問題 | No.2173 Nightcord |
| ユーザー |
 t33f
|
| 提出日時 | 2022-12-25 11:34:14 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,802 bytes |
| コンパイル時間 | 1,452 ms |
| コンパイル使用メモリ | 95,452 KB |
| 実行使用メモリ | 10,624 KB |
| 最終ジャッジ日時 | 2024-04-29 17:25:01 |
| 合計ジャッジ時間 | 5,749 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,624 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
ソースコード
#include <numeric>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
using P = pair<int, int>;
P operator-(const P lhs, const P rhs) {
return {lhs.first - rhs.first, lhs.second - rhs.second};
}
long long cp(P a, P b) {
return (long long)a.first * b.second - (long long)a.second * b.first;
}
long long dotp(P a, P b) {
return (long long)a.first * b.first + (long long)a.second * b.second;
}
vector<int> convex_hull(const vector<P> &p) {
const size_t n = p.size();
vector<int> ps(n);
iota(ps.begin(), ps.end(), 0);
sort(ps.begin(), ps.end(), [&](int i, int j) { return p[i] < p[j]; });
vector<int> lower;
for (int i : ps) {
while (lower.size() > 1) {
const size_t k = lower.size();
P cur = p[i], prev = p[lower[k-1]], pprev = p[lower[k-2]];
if (cp(prev - pprev, cur - pprev) > 0) break;
else lower.pop_back();
}
lower.push_back(i);
}
reverse(ps.begin(), ps.end());
vector<int> upper;
for (int i : ps) {
while (upper.size() > 1) {
const size_t k = upper.size();
P cur = p[i], prev = p[upper[k-1]], pprev = p[upper[k-2]];
if (cp(prev - pprev, cur - pprev) > 0) break;
else upper.pop_back();
}
upper.push_back(i);
}
lower.insert(lower.end(), upper.begin()+1, upper.end());
return lower;
}
ostream &operator<<(ostream &out, P p) {
out << p.first << ' ' << p.second;
return out;
}
bool contained_in(P c, const vector<int> &ch, const vector<P> &vs) {
assert(ch.size() == vs.size() + 1);
for (int i = 0; i < vs.size(); ++i) {
const P p = vs[ch[i]], q = vs[ch[i + 1]];
if (cp(p - c, q - c) < 0) return false;
}
return true;
}
bool check1(const vector<int> &ch, const vector<P> &vs, const vector<P> &ps) {
for (const auto &c : ps) if (contained_in(c, ch, vs)) return true;
return false;
}
inline bool segments_intersect(P p1, P q1, P p2, P q2) {
const auto [x1, y1] = p1;
const auto [z1, w1] = q1;
const auto [x2, y2] = p2;
const auto [z2, w2] = q2;
if (max(x1, z1) < min(x2, z2) || max(x2, z2) < min(x1, z1) ||
max(y1, w1) < min(y2, w2) || max(y2, w2) < min(y1, w1)) return false;
const int a1 = w1 - y1, b1 = x1 - z1, c1 = -x1 * w1 + y1 * z1,
a2 = w2 - y2, b2 = x2 - z2, c2 = -x2 * w2 + y2 * z2,
vp1 = a2 * x1 + b2 * y1 + c2,
vq1 = a2 * z1 + b2 * w1 + c2,
vp2 = a1 * x2 + b1 * y2 + c1,
vq2 = a1 * z2 + b1 * w2 + c1;
if (vp1 == 0 || vq1 == 0 || vp2 == 0 || vq2 == 0) return true;
return (vp1 > 0) != (vq1 > 0) && (vp2 > 0) != (vq2 > 0);
}
bool check2(const vector<int> &ch1, const vector<P> &vs1,
const vector<int> &ch2, const vector<P> &vs2)
{
for (int i = 0; i < vs1.size(); ++i) {
const P p1 = vs1[ch1[i]], q1 = vs1[ch1[i + 1]];
for (int j = 0; j < vs2.size(); ++j) {
const P p2 = vs2[ch2[j]], q2 = vs2[ch2[i + 1]];
if (segments_intersect(p1, q1, p2, q2)) return true;
}
}
return false;
}
bool check3(const vector<P> &ps1, const vector<P> &ps2) {
if (ps2.size() <= 1) return false;
auto compare_arg = [](P lhs, P rhs) {
const auto [x1, y1] = lhs;
const auto [x2, y2] = rhs;
const bool u1 = y1 > 0 || (y1 == 0 && x1 >= 0),
u2 = y2 > 0 || (y2 == 0 && x2 >= 0);
if (u1 != u2) return u1;
else return cp(lhs, rhs) > 0;
};
for (const P ¢er : ps1) {
vector<P> ps;
for (int j = 0; j < ps2.size(); ++j) ps.emplace_back(ps2[j] - center);
sort(ps.begin(), ps.end(), compare_arg);
// cerr << "center = " << center << endl;
for (P p : ps) cerr << p << ", "; cerr << endl;
int j = 0, m = 1;
while (j < ps.size()) {
cerr << j << endl;
while (j != m && cp(ps[j], ps[m]) > 0) if (++m == ps.size()) m = 0;
if (cp(ps[j], ps[m]) == 0 && dotp(ps[j], ps[m]) < 0) {
// cerr << center << ' ' << ps[j] << ' ' << ps[m] << endl;
return true;
}
++j;
}
}
return false;
}
int main() {
int n, k; cin >> n >> k;
vector<int> x(n), y(n), c(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> c[i];
vector<P> rp, bp;
for (int i = 0; i < n; ++i)
if (c[i] == 1) rp.emplace_back(x[i], y[i]);
else bp.emplace_back(x[i], y[i]);
const vector<int> rch = convex_hull(rp), bch = convex_hull(bp);
if (k > 3)
cout << (check1(rch, rp, bp) || check1(bch, bp, rp) || check2(bch, bp, rch, rp) ? "Yes\n": "No\n");
else
cout << (check3(rp, bp) || check3(bp, rp) ? "Yes\n": "No\n");
}