QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133394#24. Skiinghiahiahia0 0ms0kbC++14859b2023-08-02 07:24:452023-08-02 07:24:47

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 07:24:47]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-08-02 07:24:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1000010;
int n;
pair<int,int>s,t;
int x1[N],x2[N],y[N];

vector<pair<int,int>>v;
void Solve(int l,int r,pair<int,int>s,pair<int,int>t){
	if(l>r)return;
	for(int i=l;i<=r;i++){
		double px=s.first+(double)(t.first-s.first)*(y[i]-s.second)/(t.second-s.second);
		if(x1[i]<=px&&px<=x2[i])continue;
		pair<int,int>tmp={0,0};
		if(px<x1[i])tmp={x1[i],y[i]};
		else tmp={x2[i],y[i]};
		Solve(l,i-1,s,tmp);
		v.push_back(tmp);
		Solve(i+1,n,tmp,t);
		return;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	cin>>s.first>>s.second>>t.first>>t.second;
	for(int i=1;i<=n;i++)cin>>x1[i]>>x2[i]>>y[i];
	
	v.push_back(s);
	Solve(1,n,s,t);
	v.push_back(t);
	
	cout<<v.size()<<'\n';
	for(auto pr:v)cout<<pr.first<<' '<<pr.second<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 0
Memory Limit Exceeded

input:

199
175052747 997881706 -444101061 -995203708
632498445 934487489 994213208
261388064 504811653 985433204
-597252485 554801620 984846690
-571876793 -99123359 979984168
-944464963 955111086 969795165
-790384528 373348312 964934294
119986918 271285793 959808546
-98194771 361824484 953877664
-929903139...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%