Advertisement
Guest User

Untitled

a guest
May 19th, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Point
  6. {
  7. int x;
  8. int y;
  9. };
  10.  
  11. struct seg
  12. {
  13. Point p1,p2;
  14. };
  15.  
  16. bool onSegment(Point p, Point q, Point r)
  17. {
  18. if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
  19. q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
  20. return true;
  21.  
  22. return false;
  23. }
  24.  
  25. int orientation(Point p, Point q, Point r)
  26. {
  27. int val = (q.y - p.y) * (r.x - q.x) -
  28. (q.x - p.x) * (r.y - q.y);
  29.  
  30. if (val == 0) return 0;
  31.  
  32. return (val > 0)? 1: 2;
  33. }
  34.  
  35. bool doIntersect(Point p1, Point q1, Point p2, Point q2)
  36. {
  37. int o1 = orientation(p1, q1, p2);
  38. int o2 = orientation(p1, q1, q2);
  39. int o3 = orientation(p2, q2, p1);
  40. int o4 = orientation(p2, q2, q1);
  41.  
  42. if (o1 != o2 && o3 != o4)
  43. return true;
  44.  
  45. if (o1 == 0 && onSegment(p1, p2, q1)) return true;
  46.  
  47. if (o2 == 0 && onSegment(p1, q2, q1)) return true;
  48.  
  49. if (o3 == 0 && onSegment(p2, p1, q2)) return true;
  50.  
  51. if (o4 == 0 && onSegment(p2, q1, q2)) return true;
  52.  
  53. return false;
  54. }
  55.  
  56. int main()
  57. {
  58. int tc;
  59. cin>>tc;
  60. while(tc--)
  61. {
  62. int n;
  63. cin>>n;
  64. seg s[n];
  65.  
  66. for(int i=0; i<n; i++)
  67. {
  68. cin>>s[i].p1.x>>s[i].p1.y;
  69. cin>>s[i].p2.x>>s[i].p2.y;
  70. }
  71. int cnt = 0;
  72. for(int i=0; i<n; i++)
  73. {
  74. bool check = true;
  75. for(int j=0; j<n; j++)
  76. {
  77. if(i==j)
  78. continue;
  79. if(doIntersect(s[i].p1,s[i].p2,s[j].p1,s[j].p2)){
  80. check = false;
  81. break;
  82. }
  83. }
  84. if(check) cnt++;
  85. }
  86. cout<<cnt<<endl;
  87. }
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement