Submission #291193

#	Time	Username	Problem	Language	Result	Execution time	Memory
291193		TadijaSebez	Roads (CEOI20_roads)	C++11	100 / 100	206 ms	13016 KiB

roads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ldb long double
#define pb push_back
#define mp make_pair
struct pt{ll x,y;pt(ll a=0,ll b=0):x(a),y(b){}};
bool operator < (pt a,pt b){return mp(a.x,a.y)<mp(b.x,b.y);}
const int N=100050;
const int lim=1e8;
pt a[N][2];
ll tme;
ldb sec(int i){
	if(tme==a[i][0].x)return a[i][0].y;
	ldb k=(ldb)(a[i][1].y-a[i][0].y)/(a[i][1].x-a[i][0].x);
	ldb n=a[i][0].y-a[i][0].x*k;
	return tme*k+n;
}
struct seg{
	int idx;
	mutable pt rig;
	seg(){}
	seg(int i):idx(i){}
};
bool operator < (seg a,seg b){
	return sec(a.idx)<sec(b.idx);
}
set<seg> all;
int main(){
	int n;
	scanf("%i",&n);
	vector<pair<pt,int>> evs;
	for(int i=1;i<=n;i++){
		scanf("%lld %lld %lld %lld",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
		if(a[i][1]<a[i][0])swap(a[i][0],a[i][1]);
		evs.pb({a[i][0],i});
		evs.pb({a[i][1],-i});
	}
	a[n+1][0]=pt(-lim,-lim);
	a[n+1][1]=pt(lim,-lim);
	a[n+2][0]=pt(-lim,lim);
	a[n+2][1]=pt(lim,lim);
	tme=-lim;
	all.insert(seg(n+1));
	all.begin()->rig=pt(-lim,-lim);
	all.insert(seg(n+2));
	sort(evs.begin(),evs.end());
	for(auto e:evs){
		pt p=e.first;
		int i=abs(e.second);
		tme=p.x;
		if(e.second>0){
			all.insert(seg(i));
			auto it=all.find((seg(i)));
			it->rig=p;
			pt now=prev(it)->rig;
			prev(it)->rig=p;
			if(now.x!=-lim)printf("%lld %lld %lld %lld\n",now.x,now.y,p.x,p.y);
		}else{
			auto it=all.find(seg(i));
			prev(it)->rig=p;
			all.erase(it);
		}
	}
	return 0;
}

Compilation message (stderr)

roads.cpp: In function 'int main()':
roads.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
roads.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%lld %lld %lld %lld",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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