QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133394 | #24. Skiing | hiahiahia | 0 | 0ms | 0kb | C++14 | 859b | 2023-08-02 07:24:45 | 2023-08-02 07:24:47 |
Judging History
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';
}
详细
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%