제출 #668056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668056		dozer	Roads (CEOI20_roads)	C++14	30 / 100	108 ms	14984 KiB

roads

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define endl "\n"
#define sp " "
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int INF = 1e9 + 7;
const int modulo = 1e9 + 7;
int adj[N], done[N];
int x[N], y[N];
int ox[N], oy[N];

int32_t main()
{
	//fileio();
	fastio();

	int n;
	cin>>n;
	vector<int> vec;
	int a, b;
	for (int i = 1; i <= n; i++)
	{
		int x1, x2, y1, y2;
		cin>>x1>>y1>>x2>>y2;
		a = x1 - x2;
		b = y1 - y2;
		int u = 2 * i - 1, v = 2 * i;
		x[u] = x1, y[u] = y1;
		x[v] = x2, y[v] = y2;

		adj[u] = v;
		adj[v] = u;

		vec.pb(u);
		vec.pb(v);
	}
/*
	double hyp = sqrt(a * a + b * b);
	for (int i = 1; i <= 2 * n; i++)
	{
		ox[i] = x[i], oy[i] = y[i];
		if (x[i] == y[i] && x[i] == 0) continue;
		double hyp2 = sqrt(x[i] * x[i] + y[i] * y[i]);
		double cos = x[i] / hyp2, sin = y[i] / hyp2;
		
		y[i] = hyp2 * ((a / hyp) * sin + cos * (b / hyp));
		x[i] = hyp2 * ((a / hyp) * cos - sin * (b / hyp));
	}*/
	sort(vec.begin(), vec.end(), [&](int a, int b){
		return make_pair(y[a], x[a]) < make_pair(y[b], x[b]); 
	});

	//for (auto i : vec) cout<<i<<sp;
	//cout<<endl;
	vector<array<int, 4>> ans;
	set<pair<pii, int>> s;
	done[adj[vec.front()]] = 1;
	for (auto i : vec)
	{
		if (done[i] == 0 && !s.empty())
		{
			auto it = s.lower_bound({{x[i], -modulo}, 0});
			if (it == s.end()) it--;
			int ind = it->nd;
			ans.pb({x[i], y[i], x[ind], y[ind]});
			done[i] = 1;
			done[adj[i]] = 1;
		}
		else
		{
			s.erase({{x[adj[i]], y[adj[i]]}, adj[i]});
		}
		s.insert({{x[i], -y[i]}, i});
	}

	for (auto i : ans)
	{
		for (int j = 0; j < 4; j++) cout<<i[j]<<sp;
		cout<<endl;
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'int32_t main()':
roads.cpp:30:6: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   30 |  int a, b;
      |      ^
roads.cpp:30:9: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   30 |  int a, b;
      |         ^

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