fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std; 
  3. #define pdd pair<double, double> 
  4.  
  5. // this function return the intersecting point
  6. //if lines are parallel thenit returns INT_MAX
  7.  
  8. pdd displayPoint(pdd P) 
  9. { 
  10.     return make_pair(P.first,P.second);
  11. } 
  12.  
  13. pdd lineLineIntersection(pdd A, pdd B, pdd C, pdd D) 
  14. { 
  15.  
  16.     double a1 = B.second - A.second; 
  17.     double b1 = A.first - B.first; 
  18.     double c1 = a1*(A.first) + b1*(A.second); 
  19.     double a2 = D.second - C.second; 
  20.     double b2 = C.first - D.first; 
  21.     double c2 = a2*(C.first)+ b2*(C.second); 
  22.  
  23.     double determinant = a1*b2 - a2*b1; 
  24.  
  25.     if (determinant == 0) 
  26.     { 
  27.         return make_pair(INT_MAX,INT_MAX); 
  28.     } 
  29.     else
  30.     { 
  31.         double x = (b2*c1 - b1*c2)/determinant; 
  32.         double y = (a1*c2 - a2*c1)/determinant; 
  33.         return make_pair(x, y); 
  34.     } 
  35. } 
  36.  
  37.  
  38.   int main()
  39. {
  40.  int t;
  41.  cin>>t;
  42.  while(t--)
  43.  { 
  44.  
  45.  long long  int  a[100000];
  46.  long long int  x1,x2,y;
  47.  long long int n,q;
  48.   cin>>n>>q;
  49.   for(long long int i=1;i<=n;i++)
  50.   {
  51.    cin>>a[i];
  52.   }
  53.  long long int count=0;
  54.     while(q--)
  55.   {
  56.    count=0;
  57.   cin>>x1>>x2>>y;
  58.  
  59.  
  60.  for(long long int i=1;i<n;i++) 
  61.  {
  62.      pdd A = make_pair(i,a[i]);
  63.     pdd B = make_pair(i+1,a[i+1]);
  64.     pdd C = make_pair(x1, y);
  65.     pdd D = make_pair(x2,y);
  66.     pdd intersection = lineLineIntersection(A, B, C, D); 
  67.    //if lines are parallel
  68.   if (intersection.first == INT_MAX &&  intersection.second==INT_MAX) 
  69.     { 
  70.      if((y!=a[i] || y!=a[i+1]) || (i+1==x1 || i==x2) || i+1<x1 ||i>x2 )
  71.      {continue;}
  72.       count++;
  73.  
  74.     } 
  75.  
  76.     else
  77.     { 
  78.         //if lines are intersecting at a arbitary point 
  79.           pdd point =displayPoint(intersection);
  80. //to eliminate arbitary points and considering required points
  81.    if((point.first>=x1 && point.first<=x2 )&& ((a[i]>=int(point.second) && a[i+1]<=int(point.second)) || (a[i]<=int(point.second) && a[i+1]>=int(point.second))))
  82.  
  83.        {
  84.         if((i==x2 && a[i]==y)||(i+1==x1 && a[i+1]==y)){continue;} 
  85.  
  86.         count++;
  87.        }
  88.    }
  89. } 
  90. cout<<count<<endl;
  91. }
  92.  
  93. }
  94.  return 0; 
  95. }
  96.  
Success #stdin #stdout 0s 4228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1XZFux
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!