oj.uz

Submission #292932

# Submission time Handle Problem Language Result Execution time Memory
292932 2020-09-07T14:51:16 Z arnold518 Roads (CEOI20_roads) C++14
30 / 100
 240 ms 22112 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 256 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 21 ms 2684 KB Output is correct
5 Correct 39 ms 4848 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 16 ms 2684 KB Output is correct
5 Correct 33 ms 4828 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 15 ms 2684 KB Output is correct
10 Correct 240 ms 22112 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 17 ms 2676 KB Output is correct
5 Correct 38 ms 4808 KB Output is correct
6 Failed 1 ms 256 KB Condition failed: "!Cross(S[*pi], S[*pa])"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 256 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 256 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -