Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class CopyOfJ {
- FastScanner in;
- PrintWriter out;
- class O implements Comparable<O> {
- int id;
- double a, b;
- public O(int id, double a, double b) {
- super();
- this.id = id;
- this.a = a;
- this.b = b;
- }
- double get(double t) {
- return Math.sqrt(a * t + b);
- }
- @Override
- public int compareTo(O o) {
- if (Math.abs(a - o.a) > eps) {
- return -Double.compare(a, o.a);
- }
- return -Double.compare(b, o.b);
- }
- }
- class DS {
- O[] a;
- int sz;
- DS(O[] o) {
- Arrays.sort(o);
- sz = 0;
- double prevTime = 0;
- for (int i = 0; i < o.length; i++) {
- while (sz > 0) {
- double time = getT(o[sz - 1], o[i]);
- if (time <= prevTime) {
- sz--;
- if (sz >= 2) {
- prevTime = getT(o[sz - 2], o[sz - 1]);
- } else {
- prevTime = 0;
- }
- } else {
- break;
- }
- }
- o[sz++] = o[i];
- if (sz > 1) {
- prevTime = getT(o[sz - 2], o[sz - 1]);
- } else {
- prevTime = 0;
- }
- }
- a = o;
- it = 0;
- }
- int it;
- double getTime(double time) {
- while (it + 1 < sz) {
- double tt = getT(a[it], a[it + 1]);
- if (tt <= time) {
- it++;
- } else {
- break;
- }
- }
- return a[it].get(time);
- }
- }
- final double eps = 0;
- double getT(O a, O b) {
- if (Math.abs(a.a - b.a) <= eps) {
- return -1;
- }
- if (a.b >= b.b) {
- return -1;
- }
- return (b.b - a.b) / (a.a - b.a);
- }
- class Big {
- final int M = 25;
- DS[] ds = new DS[M];
- Big() {
- }
- void add(O o) {
- O[] arr = new O[] { o };
- for (int i = 0; i < M; i++) {
- if (ds[i] == null) {
- ds[i] = new DS(arr);
- return;
- } else {
- int old = arr.length;
- arr = Arrays.copyOf(arr, arr.length + ds[i].sz);
- System.arraycopy(ds[i].a, 0, arr, old, ds[i].sz);
- ds[i] = null;
- }
- }
- }
- double getTime(double t) {
- double res = Double.MAX_VALUE;
- for (int i = 0; i < M; i++) {
- if (ds[i] != null) {
- res = Math.min(res, ds[i].getTime(t));
- }
- }
- return res;
- }
- }
- void solve() {
- int tc = in.nextInt();
- for (int t = 0; t < tc; t++) {
- System.err.println("test = " + t + " / " + tc);
- int n = in.nextInt();
- int m = in.nextInt();
- int q = in.nextInt();
- Big big = new Big();
- System.err.println(n + " " + m + " " + q);
- double[] v = new double[n];
- double[] g = new double[n];
- double[] l = new double[n];
- O[] o = new O[n];
- for (int i = 0; i < m; i++) {
- v[i] = in.nextDouble();
- g[i] = in.nextDouble();
- l[i] = in.nextDouble();
- double C = l[i] * l[i];
- o[i] = new O(i, 2 * g[i] / v[i] / v[i], C / v[i] / v[i]);
- big.add(o[i]);
- }
- int cnt = 0;
- final int NEED = 5000;
- double sum = 0;
- for (int i = 0; i < q; i++) {
- String s = in.next();
- if (s.equals("Q")) {
- double time = in.nextDouble();
- cnt++;
- sum += big.getTime(time);
- if (cnt == NEED) {
- out.printf("%.15f\n", sum);
- sum = 0;
- cnt = 0;
- }
- } else {
- if (s.equals("O")) {
- double time = in.nextDouble();
- int ii = in.nextInt() - 1;
- double vv = in.nextDouble();
- double gg = in.nextDouble();
- double ll = in.nextDouble();
- double C = ll * ll - 2 * gg * time;
- O ooo = new O(i, 2 * gg / vv / vv, C / vv / vv);
- o[ii] = ooo;
- v[ii] = vv;
- big.add(ooo);
- } else {
- double time = in.nextDouble();
- int ii = in.nextInt() - 1;
- double vv = in.nextDouble();
- double gg = in.nextDouble();
- double ll = o[ii].get(time) * v[ii];
- double C = ll * ll - 2 * gg * time;
- O ooo = new O(i, 2 * gg / vv / vv, C / vv / vv);
- o[ii] = ooo;
- v[ii] = vv;
- big.add(ooo);
- }
- }
- }
- if (cnt != 0) {
- throw new AssertionError();
- }
- }
- }
- void run() {
- try {
- in = new FastScanner(new File("j2.in"));
- out = new PrintWriter(new File("j.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- double nextDouble() {
- return Double.parseDouble(next());
- }
- }
- public static void main(String[] args) {
- new CopyOfJ().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment