Guest User

Untitled

a guest
Jun 18th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.77 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Solution {
  5.     final double R = 1;
  6.     final double eps = 1e-9;
  7.     BufferedReader br;
  8.     PrintWriter out;
  9.     StringTokenizer stok;
  10.  
  11.     String nextToken() throws IOException {
  12.         String s = null;
  13.         while (stok == null || !stok.hasMoreTokens()) {
  14.             s = br.readLine();
  15.             if (s == null) {
  16.                 return "-1";
  17.             }
  18.             stok = new StringTokenizer(s);
  19.         }
  20.         return stok.nextToken();
  21.     }
  22.  
  23.     int nextInt() throws IOException {
  24.         return Integer.parseInt(nextToken());
  25.     }
  26.  
  27.     class Point implements Comparable<Point> {
  28.         double x, y;
  29.         double angle;
  30.  
  31.         Point(double x, double y, double angle) {
  32.             this.x = x;
  33.             this.y = y;
  34.             this.angle = angle;
  35.         }
  36.  
  37.         public int compareTo(Point a) {
  38.             if (Math.abs(this.x - a.x) < eps && Math.abs(this.y - a.y) < eps)
  39.                 return 0;
  40.             double t = (this.x - a.x) < eps ? this.y - a.y : this.x - a.x;
  41.             return t > 0 ? 1 : -1;
  42.         }
  43.     }
  44.  
  45.     Point getPointByAngle(int angle) {
  46.         double dangle = (double) (angle);
  47.         return new Point(R * Math.cos(dangle * Math.PI / 180), R
  48.                 * Math.sin(dangle * Math.PI / 180), dangle);
  49.     }
  50.  
  51.     class Segment {
  52.         Point a, b;
  53.  
  54.         Segment(int angle1, int angle2) {
  55.             this.a = getPointByAngle(angle1);
  56.             this.b = getPointByAngle(angle2);
  57.         }
  58.     }
  59.  
  60.     Point intersectSegments(Segment s1, Segment s2) {
  61.         double a1 = s1.b.y - s1.a.y, b1 = s1.a.x - s1.b.x;
  62.         double a2 = s2.b.y - s2.a.y, b2 = s2.a.x - s2.b.x;
  63.         double c1 = -(a1 * s1.a.x + b1 * s1.a.y), c2 = -(a2 * s2.a.x + b2
  64.                 * s2.a.y);
  65.         double x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
  66.         double y = (c2 * a1 - c1 * a2) / (-a1 * b2 + a2 * b1);
  67.         return new Point(x, y, Math.atan2(y, x));
  68.     }
  69.  
  70.     void solve() throws IOException {
  71.         int n = nextInt();
  72.         TreeMap<Point, Integer> mapPoint = new TreeMap<Point, Integer>();
  73.         Segment[] data = new Segment[n];
  74.         for (int i = 0; i < n; i++) {
  75.             int tmp1 = nextInt(), tmp2 = nextInt();
  76.             data[i] = new Segment(tmp1, tmp2);
  77.             Point tmp = getPointByAngle(tmp1);
  78.             if (!mapPoint.containsKey(tmp)) {
  79.                 mapPoint.put(tmp, 2);
  80.             } else {
  81.                 mapPoint.put(tmp, mapPoint.get(tmp) + 1);
  82.             }
  83.  
  84.             tmp = getPointByAngle(tmp2);
  85.             if (!mapPoint.containsKey(tmp)) {
  86.                 mapPoint.put(tmp, 2);
  87.             } else {
  88.                 mapPoint.put(tmp, mapPoint.get(tmp) + 1);
  89.             }
  90.         }
  91.  
  92.  
  93.         for (int i = 0; i < n; i++) {
  94.             for (int j = i + 1; j < n; j++) {
  95.                 if ((Math.min(data[i].a.angle, data[i].b.angle) <= data[j].a.angle && Math
  96.                         .max(data[i].a.angle, data[i].b.angle) >= data[j].a.angle)
  97.                         || (Math.min(data[i].a.angle, data[i].b.angle) <= data[j].b.angle && Math
  98.                                 .max(data[i].a.angle, data[i].b.angle) >= data[j].b.angle)) {
  99.                     Point tmp = intersectSegments(data[i], data[j]);
  100.                     if (Math.abs(tmp.x) - R > eps || Math.abs(tmp.y) - R > eps)
  101.                         continue;
  102.                     if (!mapPoint.containsKey(tmp)) {
  103.                         mapPoint.put(tmp, 2);
  104.                         // out.println((tmp.x / 100) + " " + (tmp.y / 100));
  105.                     } else {
  106.                         mapPoint.put(tmp, mapPoint.get(tmp) + 1);
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.         int v = mapPoint.size(), r = n;
  112.         Iterator<Integer> iterVal = mapPoint.values().iterator();
  113.         Iterator<Point> iterKey = mapPoint.keySet().iterator();
  114.  
  115.         while (iterVal.hasNext()) {
  116.             Point p = iterKey.next();
  117.             int i = iterVal.next();
  118.             if (Math.abs(p.x * p.x + p.y * p.y - R * R) < eps) {
  119.                 r++;
  120.                 continue;
  121.             }
  122.             r += (1 + (int)Math.sqrt((double) i * 8 - 7)) /2;
  123.             //out.println(i);
  124.             //out.println((p.x / 100) + " " + (p.y / 100));
  125.         }
  126.         //out.println(v + "vertex; " + r + "edge");
  127.         out.println(r - v + 1);
  128.     }
  129.  
  130.     void run() throws IOException {
  131.         br = new BufferedReader(new FileReader("input.txt"));
  132.         out = new PrintWriter("output.txt");
  133.         solve();
  134.         br.close();
  135.         out.close();
  136.     }
  137.  
  138.     public static void main(String[] args) throws IOException {
  139.         new Solution().run();
  140.  
  141.     }
  142. }
Add Comment
Please, Sign In to add comment