# 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.021 seconds