QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#13876 | #949. Roads | 123456 | 100 ✓ | 258ms | 17972kb | C++20 | 2.4kb | 2021-09-22 23:31:08 | 2022-05-17 03:13:47 |
Judging History
answer
#include <bits/stdc++.h>
#define maxN 100001
using namespace std;
struct Point{
long long x,y;
Point(long long a, long long b){x=a; y=b;}
Point(){};
};
struct Segment{
Point a, b;
Segment(){};
Segment(Point aa, Point bb){a=aa; b=bb;}
};
Segment S[maxN];
pair<int,bool> AB[2*maxN];
Point Rmost[maxN];
vector<Segment> Sol;
int n;
int Turn(Point A, Point B, Point C){
long long Kereszt=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
if (Kereszt <0)
return -1;
else if (Kereszt >0)
return 1;
else
return 0;
}
struct SegOrd{
bool operator() (const int& u, const int& v) const{
int tua=Turn(S[u].a,S[u].b,S[v].a);
int tub=Turn(S[u].a,S[u].b,S[v].b);
int tva=Turn(S[v].a,S[v].b,S[u].a);
int tvb=Turn(S[v].a,S[v].b,S[u].b);
return tua>0 && tub>0 || tva<0 && tvb<0 ||
tua==0 && tub==0&& tva==0 && tvb==0 && S[u].a.y<S[v].a.y;
}
};
set<int, SegOrd> Sline;
bool ABord(pair<int,bool> a, pair<int,bool> b){
Point ap,bp;
if(a.second) ap=S[a.first].a; else ap=S[a.first].b;
if(b.second) bp=S[b.first].a; else bp=S[b.first].b;
if(ap.x<bp.x) return true;
if(ap.x>bp.x) return false;
return (ap.y<bp.y);
}
void ReadIn(){
int x1,y1,x2,y2;
cin>>n;
for(int i=0;i<n;i++){
cin>>x1>>y1>>x2>>y2;
if(x1<x2 || x1==x2 && y1<y2)
S[i]={{x1,y1},{x2,y2}};
else
S[i]={{x2,y2},{x1,y1}};
}
}
int main(){
ReadIn();
for(int i=0;i<n;i++){
AB[i]={i,true};
AB[i+n]={i,false};
}
sort(AB, AB+2*n, ABord);
long long maxxy=10000000;
Segment sentinel={{-maxxy,-maxxy},{maxxy, -maxxy}};
S[n]=sentinel; Sline.insert(n);
int s0=AB[0].first;
Sline.insert(s0);
if(S[s0].a.x!=S[s0].b.x){
Rmost[n]=S[s0].a;
Rmost[s0]=S[s0].a;
}else{
Rmost[s0]=S[s0].b;
Rmost[n]=S[s0].b;
}
//
set<int, SegOrd>::iterator p,pp;
for(int i=1;i<2*n;i++){
if(AB[i].second){//left endpoint
p=Sline.insert(AB[i].first).first;
pp=p; pp--;
Sol.push_back({S[*p].a,Rmost[*pp]});
if(S[*p].a.x!=S[*p].b.x)
Rmost[*p]=S[*p].a;
else
Rmost[*p]=S[*p].b;
Rmost[*pp]=S[*p].a;
}else{//right endpoint
p=Sline.find(AB[i].first);
pp=p; pp--;
Rmost[*pp]=S[*p].b;
Sline.erase(p);
}
}
//
for(auto ab:Sol)
cout<<ab.a.x<<" "<<ab.a.y<<" "<<ab.b.x<<" "<<ab.b.y<<"\n";
return 0;
}
Details
Subtask #1:
score: 0
Accepted
Test #1:
score: 0
Accepted
time: 4ms
memory: 7624kb
Test #2:
score: 0
Accepted
time: 85ms
memory: 9896kb
Subtask #2:
score: 15
Accepted
Test #3:
score: 15
Accepted
time: 4ms
memory: 5720kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 7652kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 5740kb
Test #6:
score: 0
Accepted
time: 19ms
memory: 8108kb
Test #7:
score: 0
Accepted
time: 45ms
memory: 8652kb
Subtask #3:
score: 15
Accepted
Test #8:
score: 15
Accepted
time: 0ms
memory: 5740kb
Test #9:
score: 0
Accepted
time: 4ms
memory: 5664kb
Test #10:
score: 0
Accepted
time: 6ms
memory: 7716kb
Test #11:
score: 0
Accepted
time: 11ms
memory: 8048kb
Test #12:
score: 0
Accepted
time: 258ms
memory: 14176kb
Subtask #4:
score: 15
Accepted
Test #13:
score: 15
Accepted
time: 4ms
memory: 7628kb
Test #14:
score: 0
Accepted
time: 4ms
memory: 7684kb
Test #15:
score: 0
Accepted
time: 5ms
memory: 7748kb
Test #16:
score: 0
Accepted
time: 21ms
memory: 8192kb
Test #17:
score: 0
Accepted
time: 135ms
memory: 10308kb
Subtask #5:
score: 15
Accepted
Test #18:
score: 15
Accepted
time: 3ms
memory: 5692kb
Test #19:
score: 0
Accepted
time: 2ms
memory: 7836kb
Test #20:
score: 0
Accepted
time: 4ms
memory: 5736kb
Test #21:
score: 0
Accepted
time: 2ms
memory: 7636kb
Test #22:
score: 0
Accepted
time: 4ms
memory: 7692kb
Test #23:
score: 0
Accepted
time: 4ms
memory: 5780kb
Test #24:
score: 0
Accepted
time: 0ms
memory: 5752kb
Test #25:
score: 0
Accepted
time: 4ms
memory: 5724kb
Test #26:
score: 0
Accepted
time: 7ms
memory: 7964kb
Test #27:
score: 0
Accepted
time: 3ms
memory: 5776kb
Test #28:
score: 0
Accepted
time: 6ms
memory: 8060kb
Subtask #6:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #29:
score: 40
Accepted
time: 114ms
memory: 11732kb
Test #30:
score: 0
Accepted
time: 173ms
memory: 15476kb
Test #31:
score: 0
Accepted
time: 3ms
memory: 7700kb
Test #32:
score: 0
Accepted
time: 158ms
memory: 10288kb
Test #33:
score: 0
Accepted
time: 163ms
memory: 10344kb
Test #34:
score: 0
Accepted
time: 219ms
memory: 15016kb
Test #35:
score: 0
Accepted
time: 213ms
memory: 14168kb
Test #36:
score: 0
Accepted
time: 184ms
memory: 17972kb
Extra Test:
score: 0
Extra Test Passed