oj.uz

Submission #577581

# Submission time Handle Problem Language Result Execution time Memory
577581 2022-06-15T05:50:17 Z amunduzbaev Roads (CEOI20_roads) C++17
15 / 100
 135 ms 12644 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define double long double
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 4>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
		if(a[i][1] < a[i][3]) swap(a[i][0], a[i][2]), swap(a[i][1], a[i][3]);
		if(a[i][1] == a[i][3]){
			if(a[i][0] > a[i][2]) swap(a[i][0], a[i][2]), swap(a[i][1], a[i][3]);
		}
	}
	
	sort(a.begin(), a.end(), [&](auto& a, auto& b){
		if(a[1] != b[1]){
			return a[1] > b[1];
		} else {
			return a[0] < b[0];
		}
	});
	
	map<double, ar<int, 2>> mm;
	for(int i=0;i<n;i++){
		double p = a[i][0];
		if(a[i][0] != a[i][2]){
			double y = a[i][1] - a[i][3], x = a[i][0] - a[i][2];
			p = y / x;
			x = a[i][0], y = a[i][1];
			p = y - x * p;
		}
		
		if(mm.count(p)){
			cout<<a[i][0]<<" "<<a[i][1]<<" "<<mm[p][0]<<" "<<mm[p][1]<<"\n";
		}
		
		mm[p] = {a[i][2], a[i][3]};
	}
	
	ar<int, 2> last {};
	int c = 0;
	for(auto [d, p] : mm){
		if(c){
			cout<<last[0]<<" "<<last[1]<<" "<<p[0]<<" "<<p[1]<<"\n";
		}
		
		last = p;
		c = 1;
	}
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 12 ms 1584 KB Output is correct
5 Correct 23 ms 2688 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 13 ms 1516 KB Output is correct
5 Correct 24 ms 2696 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 1492 KB Output is correct
10 Failed 135 ms 12644 KB Condition failed: "!Cross(S[*pi], S[*pa])"
11 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 1492 KB Output is correct
5 Correct 25 ms 2696 KB Output is correct
6 Failed 0 ms 212 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 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
2 Halted 0 ms 0 KB -