Advertisement
konchin_shih

pC

Nov 13th, 2022
707
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<random>
  5. using namespace std;
  6. namespace {
  7.     template<typename T> using V=vector<T>;
  8.     template<typename T1,typename T2=T1> using P=pair<T1,T2>;
  9.     using ll=long long;
  10.     using lll=__int128;
  11. }
  12. constexpr int INF=0x3f3f3f3f;
  13. constexpr ll LINF=(ll)INF<<32|INF;
  14. constexpr ll maxn=1'000'000'000;
  15. struct point{ll x,y;int i;bool islow,isfront;};
  16. mt19937 mt(hash<string>()(":poop:"));
  17. struct node{
  18.    node *l,*r;
  19.    int v; point a,b;
  20.    node(point x,point y):v(mt()),a(x),b(y){
  21.        l=r=nullptr;
  22.        if(a.x>b.x) swap(a,b);
  23.    }
  24. };
  25. node* merge(node* a,node* b){
  26.    if(!a||!b) return a?:b;
  27.    if(a->v<b->v)
  28.        return a->r=merge(a->r,b),a;
  29.    return b->l=merge(a,b->l),b;
  30. }
  31. static inline lll cross(point o,point a,point b){
  32.    return (lll)(a.x-o.x)*(b.y-o.y)-(lll)(a.y-o.y)*(b.x-o.x);
  33. }
  34. void split(node* p,point k,node*& a,node*& b){
  35.    if(!p){a=b=nullptr;return;}
  36.    if(cross(p->a,k,p->b)<0)
  37.        a=p,split(a->r,k,a->r,b);
  38.    else
  39.        b=p,split(b->l,k,a,b->l);
  40. }
  41. node* find_r(node* p){
  42.    if(!p) return nullptr;
  43.    if(p->r) return find_r(p->r);
  44.    return p;
  45. }
  46. node* erase_l(node* p){
  47.    if(p->l) return p->l=erase_l(p->l),p;
  48.    return p->r;
  49. }
  50. void print(node* p){
  51.    if(!p) return;
  52.    print(p->l);
  53.    cerr<<p->a.i<<' ';
  54.    print(p->r);
  55. }
  56. static inline void solve(){
  57.    int n;ll p;cin>>n>>p;
  58.    V<P<point>> seg(n+1);
  59.    V<point> v(2*n+2);
  60.    seg[0]={point{p,maxn+1,0,true,true},point{maxn+1,maxn+2,0,false,false}};
  61.    v[0]=seg[0].first,v[1]=seg[0].second;
  62.    for(int i=1;i<=n;i++){
  63.        auto& [a,b]=seg[i];
  64.        cin>>a.x>>a.y>>b.x>>b.y;
  65.        if(a.y>b.y) swap(a,b);
  66.        a.islow=true,b.islow=false;
  67.        a.isfront=a.x<b.x;
  68.        b.isfront=b.x<a.x;
  69.        a.i=b.i=i;
  70.        v[i<<1]=a,v[i<<1|1]=b;
  71.    }
  72.    sort(v.begin(),v.end(),[](const auto& a,const auto& b){
  73.        if(a.x!=b.x) return a.x<b.x;
  74.        if(a.isfront!=b.isfront) return a.isfront>b.isfront;
  75.        return a.y<b.y;
  76.    });
  77.    V<int> e(n+1,-2);
  78.    node *l,*r,*root=nullptr;
  79.    for(auto& i:v){
  80.        split(root,i,l,r);
  81.        if(i.islow){
  82.            node* ret=find_r(l);
  83.            e[i.i]=ret?ret->a.i:-1;
  84.        }
  85.        if(i.isfront)
  86.            l=merge(l,new node(seg[i.i].first,seg[i.i].second));
  87.        else
  88.            r=erase_l(r);
  89.        root=merge(l,r);
  90. //        cerr<<":",print(root),cerr<<endl;
  91.    }
  92. //    for(auto i:e)
  93. //        cerr<<i<<' ';
  94. //    cerr<<endl;
  95.    int ans=0;
  96.    while(~e[ans]) ans=e[ans];
  97.    cout<<seg[ans].first.x<<endl;
  98. }
  99. int main(){
  100.    cin.tie(nullptr);
  101.    ios::sync_with_stdio(false);
  102.    int T=1;
  103. //    cin>>T;
  104.    while(T--)
  105.        solve();
  106.    return 0;
  107. }
  108.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement