qwerty787788

Naming

Jun 18th, 2016
546
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.41 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class CopyOfJ {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     class O implements Comparable<O> {
  9.         int id;
  10.         double a, b;
  11.  
  12.         public O(int id, double a, double b) {
  13.             super();
  14.             this.id = id;
  15.             this.a = a;
  16.             this.b = b;
  17.         }
  18.  
  19.         double get(double t) {
  20.             return Math.sqrt(a * t + b);
  21.         }
  22.  
  23.         @Override
  24.         public int compareTo(O o) {
  25.             if (Math.abs(a - o.a) > eps) {
  26.                 return -Double.compare(a, o.a);
  27.             }
  28.             return -Double.compare(b, o.b);
  29.         }
  30.  
  31.     }
  32.  
  33.     class DS {
  34.         O[] a;
  35.         int sz;
  36.  
  37.         DS(O[] o) {
  38.             Arrays.sort(o);
  39.             sz = 0;
  40.             double prevTime = 0;
  41.             for (int i = 0; i < o.length; i++) {
  42.                 while (sz > 0) {
  43.                     double time = getT(o[sz - 1], o[i]);
  44.                     if (time <= prevTime) {
  45.                         sz--;
  46.                         if (sz >= 2) {
  47.                             prevTime = getT(o[sz - 2], o[sz - 1]);
  48.                         } else {
  49.                             prevTime = 0;
  50.                         }
  51.                     } else {
  52.                         break;
  53.                     }
  54.                 }
  55.                 o[sz++] = o[i];
  56.                 if (sz > 1) {
  57.                     prevTime = getT(o[sz - 2], o[sz - 1]);
  58.                 } else {
  59.                     prevTime = 0;
  60.                 }
  61.             }
  62.             a = o;
  63.             it = 0;
  64.         }
  65.  
  66.         int it;
  67.  
  68.         double getTime(double time) {
  69.             while (it + 1 < sz) {
  70.                 double tt = getT(a[it], a[it + 1]);
  71.                 if (tt <= time) {
  72.                     it++;
  73.                 } else {
  74.                     break;
  75.                 }
  76.             }
  77.             return a[it].get(time);
  78.         }
  79.  
  80.     }
  81.  
  82.     final double eps = 0;
  83.  
  84.     double getT(O a, O b) {
  85.         if (Math.abs(a.a - b.a) <= eps) {
  86.             return -1;
  87.         }
  88.         if (a.b >= b.b) {
  89.             return -1;
  90.         }
  91.         return (b.b - a.b) / (a.a - b.a);
  92.     }
  93.  
  94.     class Big {
  95.         final int M = 25;
  96.         DS[] ds = new DS[M];
  97.  
  98.         Big() {
  99.  
  100.         }
  101.  
  102.         void add(O o) {
  103.             O[] arr = new O[] { o };
  104.             for (int i = 0; i < M; i++) {
  105.                 if (ds[i] == null) {
  106.                     ds[i] = new DS(arr);
  107.                     return;
  108.                 } else {
  109.                     int old = arr.length;
  110.                     arr = Arrays.copyOf(arr, arr.length + ds[i].sz);
  111.                     System.arraycopy(ds[i].a, 0, arr, old, ds[i].sz);
  112.                     ds[i] = null;
  113.                 }
  114.             }
  115.         }
  116.  
  117.         double getTime(double t) {
  118.             double res = Double.MAX_VALUE;
  119.             for (int i = 0; i < M; i++) {
  120.                 if (ds[i] != null) {
  121.                     res = Math.min(res, ds[i].getTime(t));
  122.                 }
  123.             }
  124.             return res;
  125.         }
  126.     }
  127.  
  128.     void solve() {
  129.         int tc = in.nextInt();
  130.         for (int t = 0; t < tc; t++) {
  131.             System.err.println("test = " + t + " / " + tc);
  132.             int n = in.nextInt();
  133.             int m = in.nextInt();
  134.             int q = in.nextInt();
  135.             Big big = new Big();
  136.             System.err.println(n + " " + m + " " + q);
  137.             double[] v = new double[n];
  138.             double[] g = new double[n];
  139.             double[] l = new double[n];
  140.             O[] o = new O[n];
  141.             for (int i = 0; i < m; i++) {
  142.                 v[i] = in.nextDouble();
  143.                 g[i] = in.nextDouble();
  144.                 l[i] = in.nextDouble();
  145.                 double C = l[i] * l[i];
  146.                 o[i] = new O(i, 2 * g[i] / v[i] / v[i], C / v[i] / v[i]);
  147.                 big.add(o[i]);
  148.             }
  149.  
  150.             int cnt = 0;
  151.             final int NEED = 5000;
  152.             double sum = 0;
  153.             for (int i = 0; i < q; i++) {
  154.                 String s = in.next();
  155.                 if (s.equals("Q")) {
  156.                     double time = in.nextDouble();
  157.                     cnt++;
  158.                     sum += big.getTime(time);
  159.                     if (cnt == NEED) {
  160.                         out.printf("%.15f\n", sum);
  161.                         sum = 0;
  162.                         cnt = 0;
  163.                     }
  164.                 } else {
  165.                     if (s.equals("O")) {
  166.                         double time = in.nextDouble();
  167.                         int ii = in.nextInt() - 1;
  168.                         double vv = in.nextDouble();
  169.                         double gg = in.nextDouble();
  170.                         double ll = in.nextDouble();
  171.                         double C = ll * ll - 2 * gg * time;
  172.                         O ooo = new O(i, 2 * gg / vv / vv, C / vv / vv);
  173.                         o[ii] = ooo;
  174.                         v[ii] = vv;
  175.                         big.add(ooo);
  176.                     } else {
  177.                         double time = in.nextDouble();
  178.                         int ii = in.nextInt() - 1;
  179.                         double vv = in.nextDouble();
  180.                         double gg = in.nextDouble();
  181.                         double ll = o[ii].get(time) * v[ii];
  182.  
  183.                         double C = ll * ll - 2 * gg * time;
  184.                         O ooo = new O(i, 2 * gg / vv / vv, C / vv / vv);
  185.                         o[ii] = ooo;
  186.                         v[ii] = vv;
  187.                         big.add(ooo);
  188.                     }
  189.                 }
  190.             }
  191.             if (cnt != 0) {
  192.                 throw new AssertionError();
  193.             }
  194.         }
  195.     }
  196.  
  197.     void run() {
  198.         try {
  199.             in = new FastScanner(new File("j2.in"));
  200.             out = new PrintWriter(new File("j.out"));
  201.  
  202.             solve();
  203.  
  204.             out.close();
  205.         } catch (FileNotFoundException e) {
  206.             e.printStackTrace();
  207.         }
  208.     }
  209.  
  210.     void runIO() {
  211.  
  212.         in = new FastScanner(System.in);
  213.         out = new PrintWriter(System.out);
  214.  
  215.         solve();
  216.  
  217.         out.close();
  218.     }
  219.  
  220.     class FastScanner {
  221.         BufferedReader br;
  222.         StringTokenizer st;
  223.  
  224.         public FastScanner(File f) {
  225.             try {
  226.                 br = new BufferedReader(new FileReader(f));
  227.             } catch (FileNotFoundException e) {
  228.                 e.printStackTrace();
  229.             }
  230.         }
  231.  
  232.         public FastScanner(InputStream f) {
  233.             br = new BufferedReader(new InputStreamReader(f));
  234.         }
  235.  
  236.         String next() {
  237.             while (st == null || !st.hasMoreTokens()) {
  238.                 String s = null;
  239.                 try {
  240.                     s = br.readLine();
  241.                 } catch (IOException e) {
  242.                     e.printStackTrace();
  243.                 }
  244.                 if (s == null)
  245.                     return null;
  246.                 st = new StringTokenizer(s);
  247.             }
  248.             return st.nextToken();
  249.         }
  250.  
  251.         boolean hasMoreTokens() {
  252.             while (st == null || !st.hasMoreTokens()) {
  253.                 String s = null;
  254.                 try {
  255.                     s = br.readLine();
  256.                 } catch (IOException e) {
  257.                     e.printStackTrace();
  258.                 }
  259.                 if (s == null)
  260.                     return false;
  261.                 st = new StringTokenizer(s);
  262.             }
  263.             return true;
  264.         }
  265.  
  266.         int nextInt() {
  267.             return Integer.parseInt(next());
  268.         }
  269.  
  270.         long nextLong() {
  271.             return Long.parseLong(next());
  272.         }
  273.  
  274.         double nextDouble() {
  275.             return Double.parseDouble(next());
  276.         }
  277.     }
  278.  
  279.     public static void main(String[] args) {
  280.         new CopyOfJ().run();
  281.     }
  282. }
Advertisement
Add Comment
Please, Sign In to add comment