oj.uz

Submission #1037989

# Submission time Handle Problem Language Result Execution time Memory
1037989 2024-07-29T11:48:25 Z vjudge1 Roads (CEOI20_roads) C++17
30 / 100
 76 ms 9664 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ar array
#define ld long double
 
const int N = 2e5 + 20;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

struct Line{
	ar<int, 2> a, b;
	Line(int x, int y, int z, int w){
		a = {x, y}, b = {z, w};
	}
	double get(){
		if(a[0] == b[0])return -a[0];
		return a[1] - a[0] * (1.0 * b[1] - a[1]) / (b[0] - a[0]);
	}
};

bool comp(Line a, Line b){
	if(abs(a.get() - b.get()) >= EPS)return a.get() > b.get();
	return a.a < b.a;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n;
	cin>>n;
	vector<Line> A;
	for(int i = 0;i < n;i++){
		int x1, y1, x2, y2;
		cin>>x1>>y1>>x2>>y2;
		if(x1 == x2){
			if(y1 > y2)swap(y1, y2), swap(x1, x2);
		}else if(x1 > x2)swap(x1, x2), swap(y1, y2);
		A.push_back(Line{x1, y1, x2, y2});
	}
	sort(A.begin(), A.end(), comp);
	for(int i = 1;i < n;i++)cout<<A[i - 1].b[0]<<" "<<A[i-1].b[1]<<" "<<A[i].a[0]<<" "<<A[i].a[1]<<'\n';
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 10 ms 988 KB Output is correct
5 Correct 12 ms 1744 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1160 KB Output is correct
5 Correct 12 ms 1752 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 1500 KB Output is correct
10 Correct 76 ms 9664 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 992 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Failed 1 ms 344 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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