QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#13876#949. Roads123456100 ✓258ms17972kbC++202.4kb2021-09-22 23:31:082022-05-17 03:13:47

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 03:13:47]
  • Judged
  • Verdict: 100
  • Time: 258ms
  • Memory: 17972kb
  • [2021-09-22 23:31:08]
  • Submitted

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