Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class Solution {
- final double R = 1;
- final double eps = 1e-9;
- BufferedReader br;
- PrintWriter out;
- StringTokenizer stok;
- String nextToken() throws IOException {
- String s = null;
- while (stok == null || !stok.hasMoreTokens()) {
- s = br.readLine();
- if (s == null) {
- return "-1";
- }
- stok = new StringTokenizer(s);
- }
- return stok.nextToken();
- }
- int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- class Point implements Comparable<Point> {
- double x, y;
- double angle;
- Point(double x, double y, double angle) {
- this.x = x;
- this.y = y;
- this.angle = angle;
- }
- public int compareTo(Point a) {
- if (Math.abs(this.x - a.x) < eps && Math.abs(this.y - a.y) < eps)
- return 0;
- double t = (this.x - a.x) < eps ? this.y - a.y : this.x - a.x;
- return t > 0 ? 1 : -1;
- }
- }
- Point getPointByAngle(int angle) {
- double dangle = (double) (angle);
- return new Point(R * Math.cos(dangle * Math.PI / 180), R
- * Math.sin(dangle * Math.PI / 180), dangle);
- }
- class Segment {
- Point a, b;
- Segment(int angle1, int angle2) {
- this.a = getPointByAngle(angle1);
- this.b = getPointByAngle(angle2);
- }
- }
- Point intersectSegments(Segment s1, Segment s2) {
- double a1 = s1.b.y - s1.a.y, b1 = s1.a.x - s1.b.x;
- double a2 = s2.b.y - s2.a.y, b2 = s2.a.x - s2.b.x;
- double c1 = -(a1 * s1.a.x + b1 * s1.a.y), c2 = -(a2 * s2.a.x + b2
- * s2.a.y);
- double x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
- double y = (c2 * a1 - c1 * a2) / (-a1 * b2 + a2 * b1);
- return new Point(x, y, Math.atan2(y, x));
- }
- void solve() throws IOException {
- int n = nextInt();
- TreeMap<Point, Integer> mapPoint = new TreeMap<Point, Integer>();
- Segment[] data = new Segment[n];
- for (int i = 0; i < n; i++) {
- int tmp1 = nextInt(), tmp2 = nextInt();
- data[i] = new Segment(tmp1, tmp2);
- Point tmp = getPointByAngle(tmp1);
- if (!mapPoint.containsKey(tmp)) {
- mapPoint.put(tmp, 2);
- } else {
- mapPoint.put(tmp, mapPoint.get(tmp) + 1);
- }
- tmp = getPointByAngle(tmp2);
- if (!mapPoint.containsKey(tmp)) {
- mapPoint.put(tmp, 2);
- } else {
- mapPoint.put(tmp, mapPoint.get(tmp) + 1);
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- if ((Math.min(data[i].a.angle, data[i].b.angle) <= data[j].a.angle && Math
- .max(data[i].a.angle, data[i].b.angle) >= data[j].a.angle)
- || (Math.min(data[i].a.angle, data[i].b.angle) <= data[j].b.angle && Math
- .max(data[i].a.angle, data[i].b.angle) >= data[j].b.angle)) {
- Point tmp = intersectSegments(data[i], data[j]);
- if (Math.abs(tmp.x) - R > eps || Math.abs(tmp.y) - R > eps)
- continue;
- if (!mapPoint.containsKey(tmp)) {
- mapPoint.put(tmp, 2);
- // out.println((tmp.x / 100) + " " + (tmp.y / 100));
- } else {
- mapPoint.put(tmp, mapPoint.get(tmp) + 1);
- }
- }
- }
- }
- int v = mapPoint.size(), r = n;
- Iterator<Integer> iterVal = mapPoint.values().iterator();
- Iterator<Point> iterKey = mapPoint.keySet().iterator();
- while (iterVal.hasNext()) {
- Point p = iterKey.next();
- int i = iterVal.next();
- if (Math.abs(p.x * p.x + p.y * p.y - R * R) < eps) {
- r++;
- continue;
- }
- r += (1 + (int)Math.sqrt((double) i * 8 - 7)) /2;
- //out.println(i);
- //out.println((p.x / 100) + " " + (p.y / 100));
- }
- //out.println(v + "vertex; " + r + "edge");
- out.println(r - v + 1);
- }
- void run() throws IOException {
- br = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter("output.txt");
- solve();
- br.close();
- out.close();
- }
- public static void main(String[] args) throws IOException {
- new Solution().run();
- }
- }
Add Comment
Please, Sign In to add comment