Advertisement
Guest User

Untitled

a guest
Sep 27th, 2016
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. //
  2. // Created by Acka on 9/22/16.
  3. //
  4.  
  5. #include <stdio.h>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. #define CCW(x1, y1, x2, y2, x3, y3) (x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3)
  10.  
  11. struct Line{ long long int x1, y1, x2, y2;
  12. void pair_swap(){
  13. if(x2 < x1){
  14. swap(x1, x2); swap(y1, y2);
  15. }
  16. }
  17.  
  18. bool cross(Line &A){
  19. long long int cross1 = get_op(CCW(x1, y1, x2, y2, A.x1, A.y1)) * get_op(CCW(x1, y1, x2, y2, A.x2, A.y2));
  20. long long int cross2 = get_op(CCW(A.x1, A.y1, A.x2, A.y2, x1, y1)) * get_op(CCW(A.x1, A.y1, A.x2, A.y2, x2, y2));
  21. return (cross1 <= 0 && cross2 <= 0);
  22. }
  23.  
  24. int get_op(long long int x){
  25. return x ? (x < 0 ? -1 : 1) : 0;
  26. }
  27.  
  28. bool operator <(const Line &A)const{
  29. return x1 == A.x1 ? x2 < A.x2 : x1 < A.x1;
  30. }
  31. };
  32.  
  33. int main()
  34. {
  35. long long int N, ans = 0; scanf("%lld", &N);
  36.  
  37. Line l[20000];
  38. for(int i = 0; i < N; i++){
  39. scanf("%lld %lld %lld %lld", &l[i].x1, &l[i].y1, &l[i].x2, &l[i].y2);
  40. l[i].pair_swap();
  41. }
  42.  
  43. sort(l, l + N);
  44.  
  45. for(long long int i = 0, miny, maxy; i < N; i++){
  46. miny = min(l[i].y1, l[i].y2);
  47. maxy = max(l[i].y1, l[i].y2);
  48.  
  49. for(int j = i + 1; j < N; j++){
  50. if(l[i].x2 < l[j].x1) break;
  51. if(max(l[j].y1, l[j].y2) < miny || maxy < min(l[j].y1, l[j].y2)) continue;
  52. if(l[i].cross(l[j])) ans++;
  53. }
  54. }
  55.  
  56. printf("%lld\n", ans);
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement