452021-01-08 21:13:34mraronRoadscpp11Elfogadva 100/100330ms38836 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1748 KiB
2Elfogadva100ms11284 KiB
subtask215/15
3Elfogadva1ms2808 KiB
4Elfogadva2ms2828 KiB
5Elfogadva4ms3060 KiB
6Elfogadva25ms5492 KiB
7Elfogadva50ms8176 KiB
subtask315/15
8Elfogadva1ms3704 KiB
9Elfogadva2ms3720 KiB
10Elfogadva4ms3952 KiB
11Elfogadva27ms6396 KiB
12Elfogadva330ms27552 KiB
subtask415/15
13Elfogadva2ms6808 KiB
14Elfogadva1ms6840 KiB
15Elfogadva4ms7064 KiB
16Elfogadva26ms9460 KiB
17Elfogadva142ms18812 KiB
subtask515/15
18Elfogadva1ms8528 KiB
19Elfogadva1ms8532 KiB
20Elfogadva2ms8568 KiB
21Elfogadva1ms8552 KiB
22Elfogadva2ms8576 KiB
23Elfogadva2ms8596 KiB
24Elfogadva4ms8776 KiB
25Elfogadva1ms8584 KiB
26Elfogadva10ms9516 KiB
27Elfogadva9ms9572 KiB
28Elfogadva21ms10344 KiB
subtask640/40
29Elfogadva140ms26760 KiB
30Elfogadva254ms31344 KiB
31Elfogadva1ms10724 KiB
32Elfogadva201ms22456 KiB
33Elfogadva197ms22460 KiB
34Elfogadva273ms28944 KiB
35Elfogadva286ms29380 KiB
36Elfogadva238ms38836 KiB