Advertisement
Guest User

Untitled

a guest
Apr 24th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long double ld;
  4. typedef long long ll;
  5. typedef pair<int,int> pii;
  6.  
  7. const int N=1<<21;
  8. int T[2*N],lazy[2*N]; //T is a max seg tree
  9. map<int,int> compr;
  10. void updateR(int ql, int qr, int val, int node=1, int nl=1, int nr=N){
  11. if (lazy[node]!=0){
  12. T[node]+=lazy[node];
  13. if (nl!=nr){
  14. lazy[2*node]+=lazy[node];
  15. lazy[2*node+1]+=lazy[node];
  16. }
  17. lazy[node]=0;
  18. }
  19. if ((qr<nl)||(nr<ql)) return;
  20. if ((ql<=nl)&&(nr<=qr)){
  21. T[node]+=val;
  22. if (nl!=nr){
  23. lazy[2*node]+=val; lazy[2*node+1]+=val;
  24. }
  25. return;
  26. }
  27. //cout<<ql<<" "<<qr<<" "<<nl<<" "<<nr<<endl;
  28. int m=(nl+nr)/2;
  29. updateR(ql,qr,val,2*node,nl,m);
  30. updateR(ql,qr,val,2*node+1,m+1,nr);
  31. T[node]=max(T[2*node],T[2*node+1]);
  32. }
  33. int query(int ql, int qr, int node=1, int nl=1, int nr=N){
  34. if (lazy[node]!=0){
  35. T[node]+=lazy[node];
  36. if (nl!=nr){
  37. lazy[2*node]+=lazy[node];
  38. lazy[2*node+1]+=lazy[node];
  39. }
  40. lazy[node]=0;
  41. }
  42. if ((ql<=nl)&&(nr<=qr)) return T[node];
  43. if ((qr<nl)||(nr<ql)) return 0;
  44. int m=(nl+nr)/2;
  45. return max(query(ql,qr,2*node,nl,m),query(ql,qr,2*node+1,m+1,nr));
  46. }
  47.  
  48. map<int,vector<pair<pii,bool>>> evs;
  49. int w,h;
  50. int conv(int x, int y){
  51. if (x==0) return y;
  52. if (y==h) return h+x;
  53. if (x==w) return h+w+(h-y);
  54. if (y==0) return h+w+h+(w-x);
  55. }
  56. int seg(ld x){
  57. if (x<=h) return 1;
  58. if (x<=h+w) return 2;
  59. if (x<=h+w+h) return 3;
  60. return 4;
  61. }
  62. pair<ld,ld> inv(ld x){
  63. if (x<=h) return {0,x};
  64. if (x<=h+w) return {x-h,h};
  65. if (x<=h+w+h) return {w,h-(x-h-w)};
  66. return {w-(x-h-w-h),0};
  67. }
  68. int main(){
  69. ios::sync_with_stdio(0);
  70. int n; cin>>n;
  71. cin>>w>>h;
  72. set<int> ys;
  73. ys.insert(0); ys.insert(h); ys.insert(h+w); ys.insert(h+w+h); ys.insert(h+w+h+w);
  74. for (int i=0;i<n;i++){
  75. int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
  76. int p1=conv(x1,y1),p2=conv(x2,y2);
  77. if (p1>p2) swap(p1,p2);
  78. vector<int> v={0,h,h+w,h+w+h,h+w+h+w};
  79. v.push_back(p1); v.push_back(p2); sort(v.begin(),v.end());
  80. vector<pii> in,out;
  81. bool good=0;
  82. for (int i=0;i<v.size()-1;i++){
  83. if (good) in.push_back({v[i],v[i+1]});
  84. else out.push_back({v[i],v[i+1]});
  85. if (v[i+1]==p1) good=1;
  86. if (v[i+1]==p2) good=0;
  87. }
  88. ys.insert(p1); ys.insert(p2);
  89. for (pii p:in) for (pii q:out) if (seg(p.first+0.5)!=seg(q.first+0.5)){
  90. //cout<<p.first<<','<<p.second<<' '<<q.first<<','<<q.second<<endl;
  91. evs[p.first].push_back({q,1});
  92. evs[p.second].push_back({q,0});
  93. evs[q.first].push_back({p,1});
  94. evs[q.second].push_back({p,0});
  95. }
  96. }
  97. vector<int> yco; yco.assign(ys.begin(),ys.end());
  98. for (int i=0;i<yco.size();i++) compr[yco[i]]=i+1;
  99. for (auto asd:evs){
  100. for (auto e:asd.second){
  101. //cout<<asd.first<<": "<<e.first.first<<" "<<e.first.second<<" "<<-1+2*e.second<<endl;
  102. updateR(compr[e.first.first],compr[e.first.second]-1,-1+2*e.second);
  103. }
  104. if (query(1,yco.size())==n){
  105. for (int i=1;i<=yco.size();i++) if (query(i,i)==n){
  106. cout<<1<<endl;
  107. pair<ld,ld> a=inv(asd.first+0.5),b=inv(yco[i-1]+0.5); //push both forward by 0.5 to be in the region
  108. cout<<a.first<<" "<<a.second<<" "<<b.first<<" "<<b.second<<endl;
  109. return 0;
  110. }
  111. }
  112. }
  113. cout<<2<<endl;
  114. cout<<0<<" "<<0.5<<" "<<w<<" "<<h-0.5<<endl;
  115. cout<<0<<" "<<h-0.5<<" "<<w<<" "<<0.5<<endl;
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement