ulvis.paste.net

Paste Search Dynamic
Recent pastes
intersection
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pdd pair<double, double>
  4. struct Point{
  5.     int x,y;
  6. };
  7.  
  8. // Utility function to find GCD of two numbers
  9. // GCD of a and b
  10. int gcd(int a, int b)
  11. {
  12.     if (b == 0)
  13.        return a;
  14.     return gcd(b, a%b);
  15. }
  16.  
  17. // Finds the no. of Integral points between
  18. // two given points.
  19. int getCount(Point p, Point q)
  20. {
  21.     // If line joining p and q is parallel to
  22.     // x axis, then count is difference of y
  23.     // values
  24.     if (p.x==q.x)
  25.         return abs(p.y - q.y) - 1;
  26.  
  27.     // If line joining p and q is parallel to
  28.     // y axis, then count is difference of x
  29.     // values
  30.     if (p.y == q.y)
  31.         return abs(p.x-q.x) - 1;
  32.  
  33.     return gcd(abs(p.x-q.x), abs(p.y-q.y))-1;
  34. }
  35.  
  36.  
  37.  
  38.  
  39. pdd lineLineIntersection(pdd A, pdd B, pdd C, pdd D)
  40. {
  41.     // Line AB represented as a1x + b1y = c1
  42.     double a1 = B.second - A.second;
  43.     double b1 = A.first - B.first;
  44.     double c1 = a1*(A.first) + b1*(A.second);
  45.  
  46.     // Line CD represented as a2x + b2y = c2
  47.     double a2 = D.second - C.second;
  48.     double b2 = C.first - D.first;
  49.     double c2 = a2*(C.first)+ b2*(C.second);
  50.  
  51.     double determinant = a1*b2 - a2*b1;
  52.  
  53.     if (determinant == 0)
  54.     {
  55.         // The lines are parallel. This is simplified
  56.         // by returning a pair of FLT_MAX
  57.         return make_pair(flt_max, flt_max);
  58.     }
  59.     else
  60.     {
  61.         double x = (b2*c1 - b1*c2)/determinant;
  62.         double y = (a1*c2 - a2*c1)/determinant;
  63.         return make_pair(x, y);
  64.     }
  65. }
  66.  
  67. int main(){
  68.     int n,x1,x2,y1,y2;
  69.     cin>>n;
  70.     Point p[n];
  71.     Point q[n];
  72.     long long sum=0;
  73.     for(int i=0;i<n;i++){
  74.         cin>>x1>>y1>>x2>>y2;
  75.         p[i].x=x1;
  76.         p[i].y=y1;
  77.         q[i].x=x2;
  78.         q[i].y=y2;
  79.         sum+=getCount(p[i],q[i])+2;
  80.     }
  81.     for(int i=0;i<n;i++){
  82.         for(int j=i+1;j<n;j++){
  83.             pdd A=make_pair(p[i].x,p[i].y);
  84.             pdd B=make_pair(q[i].x,q[i].y);
  85.             pdd C=make_pair(p[j].x,p[j].y);
  86.             pdd D=make_pair(q[j].x,q[j].y);
  87.               pdd intersection = lineLineIntersection(A, B, C, D);
  88.               cout<<intersection.first<<" "<<intersection.second<<"\n";cout<<sum<<"\n";
  89.               if (intersection.first == flt_max && intersection.second==flt_max)
  90.     {
  91.         continue;
  92.     }
  93.  
  94.     else
  95.     {
  96.       if(int(intersection.first)==intersection.first && int(intersection.second)==intersection.second){
  97.        if(intersection.first<=(max(p[i].x,q[i].x)) && intersection.first>=(min(p[i].x,q[i].x)) && intersection.second<=(max(p[i].y,q[i].y)) && intersection.second>=(min(p[i].y,q[i].y)) && intersection.first<=(max(p[j].x,q[j].x)) && intersection.first>=(min(p[j].x,q[j].x)) && intersection.second<=(max(p[j].y,q[j].y)) && intersection.second>=(min(p[j].y,q[j].y)))
  98.       sum--;
  99.       }
  100.     }
  101.     cout<<sum<<"\n";
  102.         }
  103.     }
  104.     cout<<sum;
  105. }
  106.  
  107.  
Parsed in 0.024 seconds