qwerty787788

Polygon intersection

May 22nd, 2014
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.51 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class T10 {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     final double eps = 1e-9;
  9.  
  10.     double vectMul(Point p1, Point p2, Point p3) {
  11.         return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
  12.     }
  13.  
  14.     class Point implements Comparable<Point> {
  15.         double x, y;
  16.         Point[] next;
  17.         boolean was;
  18.  
  19.         @Override
  20.         public String toString() {
  21.             return "Point [x=" + x + ", y=" + y + "]";
  22.         }
  23.  
  24.         double go() {
  25.             if (was)
  26.                 return 0.;
  27.             was = true;
  28.             Point nextP = null;
  29.             if (next[0] == null) {
  30.                 nextP = next[1];
  31.             } else {
  32.                 if (next[1] == null) {
  33.                     nextP = next[0];
  34.                 } else {
  35.                     double v = vectMul(this, next[0], next[1]);
  36.                     if (v > 0) {
  37.                         nextP = next[1];
  38.                     } else {
  39.                         nextP = next[0];
  40.                     }
  41.                 }
  42.             }
  43.             double dx = nextP.x - x;
  44.             double dy = nextP.y + y;
  45.             return nextP.go() + dx * dy;
  46.         }
  47.  
  48.         public Point(double x, double y) {
  49.             super();
  50.             this.x = x;
  51.             this.y = y;
  52.         }
  53.  
  54.         void addEdge(int type, Point n) {
  55.             if (next == null) {
  56.                 next = new Point[2];
  57.             }
  58.             next[type] = n;
  59.         }
  60.  
  61.         @Override
  62.         public int compareTo(Point o) {
  63.             if (Math.abs(x - o.x) <= eps) {
  64.                 if (Math.abs(y - o.y) <= eps)
  65.                     return 0;
  66.                 return Double.compare(y, o.y);
  67.             }
  68.             return Double.compare(x, o.x);
  69.         }
  70.  
  71.     }
  72.  
  73.     class Line {
  74.         double A, B, C;
  75.  
  76.         Line(Point a, Point b) {
  77.             A = b.y - a.y;
  78.             B = a.x - b.x;
  79.             C = -(A * a.x + B * a.y);
  80.         }
  81.  
  82.         @Override
  83.         public String toString() {
  84.             return "Line [A=" + A + ", B=" + B + ", C=" + C + "]";
  85.         }
  86.  
  87.     }
  88.  
  89.     Point intersect(Line l1, Line l2) {
  90.         double zn = l1.A * l2.B - l1.B * l2.A;
  91.         if (Math.abs(zn) < eps)
  92.             return null;
  93.         Point res = new Point(0, 0);
  94.         res.x = -(l1.C * l2.B - l1.B * l2.C) / zn;
  95.         res.y = -(l1.A * l2.C - l2.A * l1.C) / zn;
  96.         return res;
  97.     }
  98.  
  99.     double f(Point A, Point B, Point C) {
  100.         if (Math.abs(A.x - B.x) > eps) {
  101.             return (C.x - A.x) / (B.x - A.x);
  102.         }
  103.         return (C.y - A.y) / (B.y - A.y);
  104.     }
  105.  
  106.     boolean onSegment(Point A, Point B, Point C) {
  107.         if (C.x < Math.min(A.x, B.x) - eps)
  108.             return false;
  109.         if (C.x > Math.max(A.x, B.x) + eps)
  110.             return false;
  111.         if (C.y < Math.min(A.y, B.y) - eps)
  112.             return false;
  113.         if (C.y > Math.max(A.y, B.y) + eps)
  114.             return false;
  115.         return true;
  116.     }
  117.  
  118.     double sq(Point[] a) {
  119.         double s = 0.;
  120.         for (int i = 0; i < a.length; i++) {
  121.             double dx = a[i].x - a[(i + 1) % a.length].x;
  122.             double dy = a[i].y + a[(i + 1) % a.length].y;
  123.             s += dx * dy;
  124.         }
  125.         return s;
  126.     }
  127.  
  128.     boolean inside(Point a, Point[] b) {
  129.         int ins = 0;
  130.         for (int i = 0; i < b.length; i++) {
  131.             Point v = b[i];
  132.             Point u = b[(i + 1) % b.length];
  133.             if (v.y > u.y) {
  134.                 Point tmp = v;
  135.                 v = u;
  136.                 u = tmp;
  137.             }
  138.             if (vectMul(v, u, a) < 0) {
  139.                 continue;
  140.             }
  141.             double minY = Math.min(v.y, u.y), maxY = Math.max(v.y, u.y);
  142.             if (minY <= a.y + eps && maxY > a.y + eps) {
  143.                 ins = 1 - ins;
  144.             }
  145.         }
  146.         return ins == 1;
  147.     }
  148.  
  149.     void solve() {
  150.         final int n = in.nextInt();
  151.         final Point[] a = new Point[n];
  152.         for (int i = 0; i < n; i++) {
  153.             a[i] = new Point(in.nextInt(), in.nextInt());
  154.         }
  155.         if (sq(a) < 0) {
  156.             for (int l = 0, r = n - 1; l < r; l++, r--) {
  157.                 Point tmp = a[l];
  158.                 a[l] = a[r];
  159.                 a[r] = tmp;
  160.             }
  161.         }
  162.         final int m = in.nextInt();
  163.         final Point[] b = new Point[m];
  164.         for (int i = 0; i < m; i++) {
  165.             b[i] = new Point(in.nextInt(), in.nextInt());
  166.         }
  167.         if (sq(b) < 0) {
  168.             for (int l = 0, r = m - 1; l < r; l++, r--) {
  169.                 Point tmp = b[l];
  170.                 b[l] = b[r];
  171.                 b[r] = tmp;
  172.             }
  173.         }
  174.         Line[] l1 = new Line[n];
  175.         Line[] l2 = new Line[m];
  176.         for (int i = 0; i < n; i++) {
  177.             l1[i] = new Line(a[i], a[(i + 1) % n]);
  178.         }
  179.         for (int i = 0; i < m; i++) {
  180.             l2[i] = new Line(b[i], b[(i + 1) % m]);
  181.         }
  182.         ArrayList<Point>[] aa = new ArrayList[n];
  183.         for (int i = 0; i < n; i++)
  184.             aa[i] = new ArrayList<>();
  185.         ArrayList<Point>[] bb = new ArrayList[m];
  186.         for (int i = 0; i < m; i++)
  187.             bb[i] = new ArrayList<>();
  188.         int cnt2 = 0;
  189.         for (int i = 0; i < n; i++) {
  190.             for (int j = 0; j < m; j++) {
  191.                 Point inter = intersect(l1[i], l2[j]);
  192.                 if (inter != null) {
  193.                     if (onSegment(a[i], a[(i + 1) % n], inter))
  194.                         if (onSegment(b[j], b[(j + 1) % m], inter)) {
  195.                             aa[i].add(inter);
  196.                             bb[j].add(inter);
  197.                             cnt2++;
  198.                         }
  199.                 }
  200.             }
  201.         }
  202.         if (cnt2 == 0) {
  203.             if (inside(a[0], b)) {
  204.                 out.println(1);
  205.             } else {
  206.                 if (inside(b[0], a)) {
  207.                     out.println(1);
  208.                 } else {
  209.                     out.println(0);
  210.                 }
  211.             }
  212.             return;
  213.         }
  214.         for (int i = 0; i < n; i++) {
  215.             final int j = i;
  216.             aa[i].add(a[i]);
  217.             aa[i].add(a[(i + 1) % n]);
  218.             Collections.sort(aa[i], new Comparator<Point>() {
  219.  
  220.                 @Override
  221.                 public int compare(Point o1, Point o2) {
  222.                     return Double.compare(f(a[j], a[(j + 1) % n], o1),
  223.                             f(a[j], a[(j + 1) % n], o2));
  224.                 }
  225.             });
  226.             for (int k = 0; k < aa[i].size() - 1; k++) {
  227.                 aa[i].get(k).addEdge(0, aa[i].get(k + 1));
  228.             }
  229.         }
  230.         for (int i = 0; i < m; i++) {
  231.             bb[i].add(b[i]);
  232.             bb[i].add(b[(i + 1) % m]);
  233.  
  234.             final int j = i;
  235.             Collections.sort(bb[i], new Comparator<Point>() {
  236.  
  237.                 @Override
  238.                 public int compare(Point o1, Point o2) {
  239.                     return Double.compare(f(b[j], b[(j + 1) % m], o1),
  240.                             f(b[j], b[(j + 1) % m], o2));
  241.                 }
  242.             });
  243.             for (int k = 0; k < bb[i].size() - 1; k++) {
  244.                 bb[i].get(k).addEdge(1, bb[i].get(k + 1));
  245.             }
  246.         }
  247.         int cnt = 0;
  248.         for (int i = 0; i < n; i++) {
  249.             for (Point p : aa[i])
  250.                 if (p.next[0] != null && p.next[1] != null) {
  251.                     cnt += Math.abs(p.go()) > eps ? 1 : 0;
  252.                 }
  253.         }
  254.         out.println(cnt);
  255.     }
  256.  
  257.     void run() {
  258.         try {
  259.             in = new FastScanner(new File("input.txt"));
  260.             out = new PrintWriter(new File("output.txt"));
  261.  
  262.             solve();
  263.  
  264.             out.close();
  265.         } catch (FileNotFoundException e) {
  266.             e.printStackTrace();
  267.         }
  268.     }
  269.  
  270.     void runIO() {
  271.  
  272.         in = new FastScanner(System.in);
  273.         out = new PrintWriter(System.out);
  274.  
  275.         solve();
  276.  
  277.         out.close();
  278.     }
  279.  
  280.     class FastScanner {
  281.         BufferedReader br;
  282.         StringTokenizer st;
  283.  
  284.         public FastScanner(File f) {
  285.             try {
  286.                 br = new BufferedReader(new FileReader(f));
  287.             } catch (FileNotFoundException e) {
  288.                 e.printStackTrace();
  289.             }
  290.         }
  291.  
  292.         public FastScanner(InputStream f) {
  293.             br = new BufferedReader(new InputStreamReader(f));
  294.         }
  295.  
  296.         String next() {
  297.             while (st == null || !st.hasMoreTokens()) {
  298.                 String s = null;
  299.                 try {
  300.                     s = br.readLine();
  301.                 } catch (IOException e) {
  302.                     e.printStackTrace();
  303.                 }
  304.                 if (s == null)
  305.                     return null;
  306.                 st = new StringTokenizer(s);
  307.             }
  308.             return st.nextToken();
  309.         }
  310.  
  311.         boolean hasMoreTokens() {
  312.             while (st == null || !st.hasMoreTokens()) {
  313.                 String s = null;
  314.                 try {
  315.                     s = br.readLine();
  316.                 } catch (IOException e) {
  317.                     e.printStackTrace();
  318.                 }
  319.                 if (s == null)
  320.                     return false;
  321.                 st = new StringTokenizer(s);
  322.             }
  323.             return true;
  324.         }
  325.  
  326.         int nextInt() {
  327.             return Integer.parseInt(next());
  328.         }
  329.  
  330.         long nextLong() {
  331.             return Long.parseLong(next());
  332.         }
  333.     }
  334.  
  335.     public static void main(String[] args) {
  336.         new T10().run();
  337.     }
  338. }
Advertisement
Add Comment
Please, Sign In to add comment