Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5. ifstream fin("diagonala.in");
  6. ofstream fout("diagonala.out");
  7.  
  8. const int nmx=200005;
  9. int n,i,j,p,nr,rez;
  10.  
  11. struct Seg
  12. { int x,y; } filn[nmx],ln[nmx];
  13.  
  14. int intersect(Seg a,Seg b)
  15. {
  16. if(max(a.x,b.x)<=min(a.y,b.y)) return 1;
  17. return 0;
  18. }
  19.  
  20. void solve()
  21. {
  22. p=1;
  23. for(i=2;i<=n;i++)
  24. {
  25. while(intersect(ln[i],ln[p])==0)
  26. p++;
  27. rez=max(rez,i-p+1);
  28. }
  29. }
  30.  
  31. int main() {
  32.  
  33. fin>>n;
  34. for(i=1;i<=n;i++)
  35. fin>>filn[i].x>>filn[i].y;
  36.  
  37. rez=1;
  38.  
  39. for(i=1;i<=n;i++)
  40. ln[i]={filn[i].x+(i-1), filn[i].y+(i-1)};
  41.  
  42. solve();
  43.  
  44. for(i=n;i>=1;i--)
  45. ln[i]={filn[i].x+(n-i), filn[i].y+(n-i)};
  46.  
  47. solve();
  48.  
  49. fout<<rez<<"\n";
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement