Advertisement
Guest User

Opencup 22.11.2015, problem I

a guest
Nov 23rd, 2015
496
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.26 KB | None | 0 0
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.io.BufferedWriter;
  7. import java.io.Writer;
  8. import java.io.OutputStreamWriter;
  9. import java.util.InputMismatchException;
  10. import java.io.IOException;
  11. import java.io.InputStream;
  12.  
  13. /**
  14.  * Built using CHelper plug-in
  15.  * Actual solution is at the top
  16.  *
  17.  * @author ilyakor
  18.  */
  19. public class Main {
  20.     public static void main(String[] args) {
  21.         InputStream inputStream = System.in;
  22.         OutputStream outputStream = System.out;
  23.         InputReader in = new InputReader(inputStream);
  24.         OutputWriter out = new OutputWriter(outputStream);
  25.         TaskI solver = new TaskI();
  26.         solver.solve(1, in, out);
  27.         out.close();
  28.     }
  29.  
  30.     static class TaskI {
  31.         int x1;
  32.         int y1;
  33.         int x2;
  34.         int y2;
  35.         int cnt;
  36.         final int MAX = 505;
  37.         final double eps = 1e-6;
  38.         int[][] used;
  39.         int[][] rad;
  40.  
  41.         public double pointToSegmentDistance(int x, int y) {
  42.             int dx = x2 - x1;
  43.             int dy = y2 - y1;
  44.             int px = x - x1;
  45.             int py = y - y1;
  46.             int squaredLength = dx * dx + dy * dy;
  47.             double k = dx * px + dy * py;
  48.             if (k < 0 || squaredLength == 0) {
  49.                 return sqHypot(px, py);
  50.             }
  51.             if (k > squaredLength) {
  52.                 return sqHypot(px - dx, py - dy);
  53.             }
  54.             k /= squaredLength;
  55.             return sqHypot(px - k * dx, py - k * dy);
  56.         }
  57.  
  58.         private double sqHypot(double px, double py) {
  59.             return px * px + py * py;
  60.         }
  61.  
  62.         public void solve(int testNumber, InputReader in, OutputWriter out) {
  63.             int n = in.nextInt();
  64.             used = new int[MAX][MAX];
  65.             rad = new int[MAX][MAX];
  66.             for (int x = 0; x < MAX; ++x)
  67.                 for (int y = 0; y < MAX; ++y)
  68.                     used[x][y] = -1;
  69.             for (int i = 0; i < n; ++i) {
  70.                 int x = in.nextInt(), y = in.nextInt(), r = (int) (in.nextDouble() * 10);
  71.                 used[x][y] = 0;
  72.                 rad[x][y] = r * r;
  73.             }
  74.             int q = in.nextInt();
  75.             for (int it = 1; it <= q; ++it) {
  76.                 x1 = in.nextInt();
  77.                 y1 = in.nextInt();
  78.                 x2 = in.nextInt();
  79.                 y2 = in.nextInt();
  80.                 cnt = 0;
  81.                 int a = y2 - y1, b = x1 - x2, c = -a * x1 - b * y1;
  82.                 int curx = x1, cury = y1, dirx = (int) Math.signum(x2 - x1), diry = (int) Math.signum(y2 - y1);
  83.                 while ((curx != x2) || (cury != y2)) {
  84.                     check(curx, cury, it);
  85.                     check(curx + dirx, cury, it);
  86.                     check(curx, cury + diry, it);
  87.                     if ((diry != 0) && (getD(a, b, c, curx, cury + diry) * getD(a, b, c, curx + dirx, cury + diry) <= 0))
  88.                         cury += diry;
  89.                     else
  90.                         curx += dirx;
  91.                 }
  92.                 check(x2, y2, it);
  93.                 out.printLine(cnt);
  94.             }
  95.         }
  96.  
  97.         private void check(int x, int y, int it) {
  98.             if ((x < 0) || (x >= MAX) || (y < 0) || (y >= MAX) || (used[x][y] < 0) || (used[x][y] == it)) return;
  99.             used[x][y] = it;
  100.             if (pointToSegmentDistance(x, y) * 100 <= rad[x][y] + eps)
  101.                 cnt++;
  102.         }
  103.  
  104.         private int getD(int a, int b, int c, int x, int y) {
  105.             int d = a * x + b * y + c;
  106.             if (d < 0) return -1;
  107.             if (d > 0) return 1;
  108.             return 0;
  109.         }
  110.  
  111.     }
  112.  
  113.     static class OutputWriter {
  114.         private final PrintWriter writer;
  115.  
  116.         public OutputWriter(OutputStream outputStream) {
  117.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  118.         }
  119.  
  120.         public OutputWriter(Writer writer) {
  121.             this.writer = new PrintWriter(writer);
  122.         }
  123.  
  124.         public void print(Object... objects) {
  125.             for (int i = 0; i < objects.length; i++) {
  126.                 if (i != 0) {
  127.                     writer.print(' ');
  128.                 }
  129.                 writer.print(objects[i]);
  130.             }
  131.         }
  132.  
  133.         public void printLine(Object... objects) {
  134.             print(objects);
  135.             writer.println();
  136.         }
  137.  
  138.         public void close() {
  139.             writer.close();
  140.         }
  141.  
  142.     }
  143.  
  144.     static class InputReader {
  145.         private InputStream stream;
  146.         private byte[] buffer = new byte[10000];
  147.         private int cur;
  148.         private int count;
  149.  
  150.         public InputReader(InputStream stream) {
  151.             this.stream = stream;
  152.         }
  153.  
  154.         public static boolean isSpace(int c) {
  155.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  156.         }
  157.  
  158.         public int read() {
  159.             if (count == -1) {
  160.                 throw new InputMismatchException();
  161.             }
  162.             try {
  163.                 if (cur >= count) {
  164.                     cur = 0;
  165.                     count = stream.read(buffer);
  166.                     if (count <= 0)
  167.                         return -1;
  168.                 }
  169.             } catch (IOException e) {
  170.                 throw new InputMismatchException();
  171.             }
  172.             return buffer[cur++];
  173.         }
  174.  
  175.         public int readSkipSpace() {
  176.             int c;
  177.             do {
  178.                 c = read();
  179.             } while (isSpace(c));
  180.             return c;
  181.         }
  182.  
  183.         public int nextInt() {
  184.             int sgn = 1;
  185.             int c = readSkipSpace();
  186.             if (c == '-') {
  187.                 sgn = -1;
  188.                 c = read();
  189.             }
  190.             int res = 0;
  191.             do {
  192.                 if (c < '0' || c > '9') {
  193.                     throw new InputMismatchException();
  194.                 }
  195.                 res = res * 10 + c - '0';
  196.                 c = read();
  197.             } while (!isSpace(c));
  198.             res *= sgn;
  199.             return res;
  200.         }
  201.  
  202.         public double nextDouble() {
  203.             double sgn = 1;
  204.             int c = readSkipSpace();
  205.             if (c == '-') {
  206.                 sgn = -1;
  207.                 c = read();
  208.             }
  209.             double res = 0;
  210.             while (!isSpace(c) && c != '.') {
  211.                 if (c == 'e' || c == 'E') {
  212.                     return res * Math.pow(10, nextInt());
  213.                 } else if (c < '0' || c > '9') {
  214.                     throw new InputMismatchException();
  215.                 }
  216.                 res = res * 10 + c - '0';
  217.                 c = read();
  218.             }
  219.             if (c == '.') {
  220.                 c = read();
  221.                 double m = 1;
  222.                 while (!isSpace(c)) {
  223.                     if (c == 'e' || c == 'E') {
  224.                         return res * Math.pow(10, nextInt());
  225.                     } else if (c < '0' || c > '9') {
  226.                         throw new InputMismatchException();
  227.                     }
  228.                     m /= 10;
  229.                     res += (c - '0') * m;
  230.                     c = read();
  231.                 }
  232.             }
  233.             res *= sgn;
  234.             return res;
  235.         }
  236.  
  237.     }
  238. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement