Submission #1298656

#TimeUsernameProblemLanguageResultExecution timeMemory
1298656PieArmyRoads (CEOI20_roads)C++20
0 / 100
2 ms14520 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n;
pair<pair<int,int>,pair<int,int>>arr[100023];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i].fr.fr>>arr[i].fr.sc>>arr[i].sc.fr>>arr[i].sc.sc;
		if(arr[i].fr>arr[i].sc)swap(arr[i].fr,arr[i].sc);
	}
	bool subtask=true;
	for(int i=0;i<n;i++){
		if(arr[i].fr.fr!=arr[i].sc.fr||arr[i].fr.sc!=arr[i].sc.sc)subtask=false;
	}
	if(subtask){
		map<int,vector<pair<int,int>>>mp;
		map<int,int>st;
		for(int i=0;i<n;i++){
			mp[arr[i].fr.sc].pb({arr[i].fr.fr,1});
			if(arr[i].fr.sc==arr[i].sc.sc){
				mp[arr[i].sc.sc].pb({arr[i].sc.fr,0});
			}
			else mp[arr[i].sc.sc].pb({arr[i].sc.fr,-1});
		}
		for(auto&[y,v]:mp){
			sort(v.begin(),v.end());
			pair<int,int>las={23,2};
			for(auto p:v){
				if(p.sc==1){
					if(st.size()){
						auto itr=st.lower_bound(p.fr);
						if(itr==st.end()){
							itr--;
						}
						cout<<p.fr<<" "<<y<<" "<<itr->fr<<" "<<itr->sc<<endl;
					}
					else if(las.sc!=2){
						cout<<p.fr<<" "<<y<<" "<<las.fr<<" "<<y<<endl;
					}
				}
				las=p;
			}
			for(auto p:v){
				st[p.fr]=y;
				if(p.sc==0){
					while(true){
						auto itr=--st.lower_bound(p.fr);
						if(itr->fr==las.fr)break;
						st.erase(itr);
					}
				}
				las=p;
			}
		}
		return 0;
	}
	subtask=true;
	if(subtask){
		sort(arr,arr+n,[&](const pair<pair<int,int>,pair<int,int>>&x,const pair<pair<int,int>,pair<int,int>>&y){
			double a=x.fr.sc-double(x.sc.sc-x.fr.sc)*(double(x.fr.fr)/double(x.sc.fr-x.fr.fr));
			double b=y.fr.sc-double(y.sc.sc-y.fr.sc)*(double(y.fr.fr)/double(y.sc.fr-y.fr.fr));

			return a<b;
		});
		for(int i=0;i<n-1;i++){
			cout<<arr[i].fr.fr<<" "<<arr[i].fr.sc<<" "<<arr[i+1].sc.fr<<" "<<arr[i+1].sc.sc<<endl;
		}
		return 0;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...