QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115160 | #5419. Triangles | UrgantTeam# | WA | 6ms | 3524kb | C++23 | 5.5kb | 2023-06-24 18:53:55 | 2023-06-24 18:53:56 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#define x first
#define y second
#include <iostream>
#include <vector>
#include <tuple>
#include <random>
#include <cmath>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;
using ll = long long;
using tri = tuple<pii, pii, pii>;
using vtri = vector<tri>;
using pdd = pair<double, double>;
ll gcd(ll a, ll b) {
while (b) {
a %= b;
swap(a, b);
}
return abs(a);
}
ll operator*(pii a, pii b) {
return ll(a.x) * b.x + ll(a.y) * b.y;
}
ll operator%(pii a, pii b) {
return ll(a.x) * b.y - ll(a.y) * b.x;
}
pii operator-(const pii a, const pii b) {
return { a.x - b.x, a.y - b.y };
}
pii operator+(const pii a, const pii b) {
return { a.x + b.x, a.y + b.y };
}
pii& operator/=(pii& a, const int b) {
return a = { a.x / b, a.y / b };
}
pii operator/(pii a, const int b) {
return a /= b;
}
bool acute_angle(pii a, pii b) {
return a * b > 0;
}
bool acute_angle(pii a, pii b, pii c) {
return acute_angle(a - b, c - b);
}
bool acute_triangle(const tri& t) {
return acute_angle(get<0>(t), get<1>(t), get<2>(t)) &&
acute_angle(get<1>(t), get<2>(t), get<0>(t)) &&
acute_angle(get<2>(t), get<0>(t), get<1>(t));
}
bool acute_triangles(const vtri& v) {
for (const tri& t : v) if (!acute_triangle(t)) return false;
return true;
}
const int N = 1000000000;
const int BIG = 32, SMALL = 1;
mt19937 rng;
pii point_on_seg(pii a, pii b, int y) {
int g = gcd(a.x - b.x, a.y - b.y);
g /= gcd(g, y);
uniform_int_distribution<int> d(1, max(g - 1, 1));
int l = d(rng);
return { a.x + (b.x - a.x) / g * l, a.y + (b.y - a.y) / g * l };
}
vtri try_find_partially_obtuse_ans(const int k) {
pii a = { 0, 0 }, b = { N, 0 }, c = { N, N }, d = { 0, N };
if (k == 4) {
pii e = c / 2;
pii f = d / 2;
pii g = point_on_seg(e, f, BIG);
return {
{a, b, g},
{b, c, g},
{c, d, g},
{g, d, a},
};
}
if (k == 5) {
pii e = c / 2;
pii f = d / 2;
pii g = point_on_seg(e, f, BIG);
pii q = point_on_seg(f, d, BIG);
return {
{a, b, g},
{b, c, g},
{c, d, g},
{q, a, g},
{q, g, d},
};
}
if (k == 6) {
pii e = c / 2;
pii f = d / 2;
pii h = point_on_seg(a, e, BIG);
pii s = point_on_seg(f, a, BIG);
pii ss = { s.y, s.x };
return {
{ss, b, h},
{h, b, c},
{d, h, c},
{s, h, d},
{s, ss, h},
{a, ss, s},
};
}
return {};
}
bool ccw(pii a, pii b) {
return a % b > 0;
}
bool ccw(pii a, pii b, pii c) {
return ccw(c - b, a - b);
}
bool inside(pii a, pii b, pii c, pii z) {
return ccw(a, b, z) && ccw(b, c, z) && ccw(c, a, z);
}
pii point_in_tri(pii a, pii b, pii c) {
while (true) {
uniform_real_distribution<double> d(0, 1);
double A = d(rng), B = d(rng), C = d(rng);
double S = A + B + C; A /= S; B /= S; C /= S;
pdd z{ a.x * A + b.x * B + c.x * C, a.y * A + b.y * B + c.y * C };
pii zz{ round(z.x), round(z.y) };
if (inside(a, b, c, z)) return zz;
}
}
vtri try_to_break(const tri& t) { // first angle is obtuse, all triangles are ccw
pii a = get<0>(t), b = get<1>(t), c = get<2>(t);
for (int i = 0; i < 30; ++i) {
pii e = point_on_seg(a, b, SMALL);
pii f = point_on_seg(b, c, SMALL);
pii g = point_on_seg(f, c, SMALL);
pii h = point_on_seg(a, c, SMALL);
pii d = point_in_tri(a, b, c);
vtri ans = {
{a, e, d},
{b, f, e},
{f, d, e},
{f, g, d},
{g, c, h},
{g, h, d},
{d, h, a},
};
if (acute_triangles(ans)) return ans;
}
return {};
}
vtri try_divide(const tri& t, const int k) {
if (k == 4) {
pii ab = get<1>(t) - get<0>(t);
pii ac = get<2>(t) - get<0>(t);
if (ab.x % 2 || ab.y % 2 || ac.x % 2 || ac.y % 2) return {};
ab /= 2;
ac /= 2;
pii a = get<0>(t), b = get<1>(t), c = get<2>(t);
pii A = get<0>(t) + ab + ac, B = get<0>(t) + ac, C = get<0>(t) + ab;
return {
{a, C, B},
{b, A, C},
{c, B, A},
{A, B, C},
};
}
else
return {};
}
vtri try_find_ans(const int k) {
if (k <= 12) {
vtri ans = try_find_partially_obtuse_ans(k - 6);
if (ans.empty()) return {};
tri last = ans.back();
ans.pop_back();
vtri broken = try_to_break(last);
if (broken.empty()) return {};
for (const tri& t : broken) ans.push_back(t);
if (!acute_triangles(ans)) return {};
return ans;
}
vtri ans = try_find_ans(k - 3);
if (ans.empty()) return {};
for (int i = 0; i < ans.size(); ++i) {
vtri g = try_divide(ans[i], 4);
if (!g.empty()) {
ans.erase(ans.begin() + i);
for (const tri& t : g) ans.push_back(t);
return ans;
}
}
return {};
}
vtri find_ans(const int k) {
if (k <= 9) return {};
while (true) {
vtri t = try_find_ans(k);
if (!t.empty())
return t;
}
}
ostream& operator<<(ostream& out, const pii& p) {
return out << p.x << ' ' << p.y;
}
ostream& operator<<(ostream& out, const tri& t) {
return out << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);
}
void solve() {
int k;
cin >> k;
vtri ans = find_ans(k);
if (ans.empty()) cout << "No\n";
else {
cout << "Yes\n";
for (const tri& t : ans)
cout << t << '\n';
}
}
void stress() {
for (int k = 10; k <= 50; ++k) {
vtri ans = find_ans(k);
cerr << k << " is ";
if (acute_triangles(ans) && ans.size() == k) {
cerr << "OK\n";
}
else {
cerr << "FAIL\n";
return;
}
}
}
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef ONPC
stress();
#endif
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3424kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 6ms
memory: 3500kb
input:
24
output:
Yes 0 188197952 188197952 0 311791328 311791328 0 0 102209124 0 90323183 38849135 188197952 0 137443842 50754110 102209124 0 137443842 50754110 90323183 38849135 102209124 0 137443842 50754110 85394515 102803437 90323183 38849135 85394515 102803437 0 188197952 0 70185343 85394515 102803437 0 7018534...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
6
output:
No
result:
ok no solution
Test #8:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 3524kb
input:
8
output:
No
result:
wrong answer feasible solution not found