Submission #1216850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216850		MateiKing80	Roads (CEOI20_roads)	C++20	15 / 100	27 ms	1608 KiB

roads

#include <bits/extc++.h>

using namespace std;

using ld = long double;
using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second


pii pts[200000];
int dx, dy;

bool cmp(pii a, pii b) {
	long double ca = (ld(a.sc) / ld(dy)) * dx + a.fr;
	long double cb = (ld(b.sc) / ld(dy)) * dx + b.fr;
	if (ca == cb)
		return a < b;
	return ca < cb;
}

signed main() {  
	int n;
	cin >> n;
	for (int i = 0; i < 2 * n; i ++)
		cin >> pts[i].fr >> pts[i].sc;
	dx = pts[0].fr - pts[1].fr;
	if (dx < 0)
		for (int i = 0; i < 2 * n; i += 2)
			swap(pts[i], pts[i + 1]);
	dy = pts[0].sc - pts[1].sc;
	int sus = abs(__gcd(dx, dy));
	dx /= sus;
	dy /= sus;
	sort(pts, pts + 2 * n, cmp);
	for (int i = 0; i < n - 1; i ++)
		cout << pts[2 * i + 1].fr << " " << pts[2 * i + 1].sc << " " << pts[2 * i + 2].fr << " " << pts[2 * i + 2].sc << '\n';
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40