QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115160#5419. TrianglesUrgantTeam#WA 6ms3524kbC++235.5kb2023-06-24 18:53:552023-06-24 18:53:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 18:53:56]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3524kb
  • [2023-06-24 18:53:55]
  • 提交

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