Submission #292932

#	Time	Username	Problem	Language	Result	Execution time	Memory
292932		arnold518	Roads (CEOI20_roads)	C++14	30 / 100	240 ms	22112 KiB

roads

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct Point
{
	ll x, y;
};

struct Line
{
	Point p, q;
};

Point operator + (const Point &p, const Point &q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }
ll dot(const Point &p, const Point &q) { return p.x*q.x+p.y*q.y; }

bool operator < (const Point &p, const Point &q)
{
	if(p.x==q.x) return p.y<q.y;
	return p.x<q.x;
}

bool operator > (const Point &p, const Point &q)
{
	if(p.x==q.x) return p.y>q.y;
	return p.x>q.x;
}

int N;
Line A[MAXN+10];
map<ll, vector<Line>> M;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &A[i].p.x, &A[i].p.y, &A[i].q.x, &A[i].q.y);

	Point L=A[1].p-A[1].q;
	swap(L.x, L.y); L.x*=-1;

	for(int i=1; i<=N; i++) M[dot(A[i].p, L)].push_back(A[i]);

	vector<Line> ans;
	for(auto &it : M)
	{
		vector<Line> &V=it.second;
		for(auto &jt : V) if(jt.p>jt.q) swap(jt.p, jt.q);
		sort(V.begin(), V.end(), [&](const Line &pp, const Line &qq) { return pp.p<qq.p; });
		for(int i=0; i+1<V.size(); i++) ans.push_back({V[i].q, V[i+1].p});
	}
	for(auto it=M.begin(); next(it)!=M.end(); it++) ans.push_back({it->second[0].p, next(it)->second[0].p});
	for(auto it : ans) printf("%lld %lld %lld %lld\n", it.p.x, it.p.y, it.q.x, it.q.y);
}

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=0; i+1<V.size(); i++) ans.push_back({V[i].q, V[i+1].p});
      |                ~~~^~~~~~~~~
roads.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
roads.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  for(int i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &A[i].p.x, &A[i].p.y, &A[i].q.x, &A[i].q.y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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