412021-01-08 20:34:07mraronRoadscpp11Accepted 100/100314ms52776 KiB
#include <bits/stdc++.h>
#define   maxN  300001

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;
  if(a.second && !b.second) return true;
  if(!a.second && b.second) 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1748 KiB
2Accepted101ms11264 KiB
subtask215/15
3Accepted1ms2880 KiB
4Accepted2ms2912 KiB
5Accepted4ms3140 KiB
6Accepted25ms5536 KiB
7Accepted52ms8300 KiB
subtask315/15
8Accepted1ms3828 KiB
9Accepted2ms3852 KiB
10Accepted4ms4088 KiB
11Accepted27ms6580 KiB
12Accepted314ms27964 KiB
subtask415/15
13Accepted1ms7176 KiB
14Accepted1ms7196 KiB
15Accepted4ms7404 KiB
16Accepted28ms9836 KiB
17Accepted162ms19412 KiB
subtask515/15
18Accepted1ms9020 KiB
19Accepted1ms9032 KiB
20Accepted2ms9044 KiB
21Accepted2ms9052 KiB
22Accepted2ms9088 KiB
23Accepted2ms9084 KiB
24Accepted3ms9292 KiB
25Accepted1ms9088 KiB
26Accepted10ms10036 KiB
27Accepted9ms10096 KiB
28Accepted18ms10988 KiB
subtask640/40
29Accepted140ms27380 KiB
30Accepted223ms33164 KiB
31Accepted1ms12488 KiB
32Accepted195ms26340 KiB
33Accepted193ms28604 KiB
34Accepted257ms38196 KiB
35Accepted291ms41596 KiB
36Accepted231ms52776 KiB