Advertisement
Guest User

Untitled

a guest
May 30th, 2015
243
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.36 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class B {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     class Water {
  9.         double r, c;
  10.  
  11.         public Water(double r, double c) {
  12.             super();
  13.             this.r = r;
  14.             this.c = c;
  15.         }
  16.     }
  17.  
  18.     public void solve() throws IOException {
  19.         Locale.setDefault(Locale.US);
  20.         int n = in.nextInt();
  21.         double v = in.nextDouble(), x = in.nextDouble();
  22.         ArrayList<Water> ws = new ArrayList<>();
  23.         TreeMap<Double, Double> cws = new TreeMap<>();
  24.         for (int i = 0; i < n; i++) {
  25.             double r = in.nextDouble(), c = in.nextDouble();
  26.             if (cws.containsKey(c))
  27.                 r += cws.get(c);
  28.             cws.put(c, r);
  29.         }
  30.         for (double c : cws.keySet()) {
  31.             ws.add(new Water(cws.get(c), c));
  32.         }
  33.         n = ws.size();
  34.         Collections.sort(ws, new Comparator<Water>() {
  35.  
  36.             @Override
  37.             public int compare(Water arg0, Water arg1) {
  38.                 return Double.compare(arg0.c, arg1.c);
  39.             }
  40.         });
  41.         if (x > ws.get(n - 1).c || x < ws.get(0).c) {
  42.             out.println("IMPOSSIBLE");
  43.             return;
  44.         }
  45.         double canNeg = 0, canPos = 0;
  46.         double sumNegR = 0, sumPosR = 0;
  47.         double sumNeutralR = 0;
  48.         for (Water w : ws) {
  49.             if (w.c < x) {
  50.                 sumNegR += w.r;
  51.                 canNeg += (x - w.c) * w.r;
  52.             } else if (w.c > x) {
  53.                 sumPosR += w.r;
  54.                 canPos += (w.c - x) * w.r;
  55.             } else if (w.c == x) {
  56.                 sumNeutralR += w.r;
  57.             }
  58.         }
  59.         if (sumPosR > 0 && sumNegR > 0) {
  60.             canPos /= sumPosR;
  61.             canNeg /= sumNegR;
  62.             double alphaNeg = canPos / (canNeg + canPos);
  63.             double tRes = -1;
  64.             {
  65.                 double tNeg = alphaNeg * v / sumNegR, tPos = (1 - alphaNeg) * v
  66.                         / sumPosR;
  67.                 tRes = Math.max(tNeg, tPos);
  68.             }
  69.             if (sumNeutralR != 0) {
  70.                 System.err.println("TRICKY TEST");
  71.                 double tl = 0, tr = tRes;
  72.                 for (int iter = 0; iter < 100; iter++) {
  73.                     double tm = (tl + tr) / 2;
  74.                     double restV = Math.max(0, v - tm * sumNeutralR);
  75.                     double tNeg = alphaNeg * restV / sumNegR, tPos = (1 - alphaNeg)
  76.                             * restV / sumPosR;
  77.                     if (tNeg <= tm && tPos <= tm) {
  78.                         tr = tm;
  79.                     } else {
  80.                         tl = tm;
  81.                     }
  82.                 }
  83.                 tRes = tl;
  84.             }
  85.             out.println(tRes);
  86.         } else {
  87.             out.println(v / sumNeutralR);
  88.         }
  89.         /*
  90.          * double alpha = (x - ws.get(0).c) / (ws.get(1).c - ws.get(0).c);
  91.          * double v1 = v * alpha, v0 = v * (1 - alpha); double res = Math.max(v0
  92.          * / ws.get(0).r, v1 / ws.get(1).r); out.println(res);
  93.          */
  94.     }
  95.  
  96.     public void run() {
  97.         try {
  98.             in = new FastScanner(new File("a.in"));
  99.             out = new PrintWriter(new File("a.out"));
  100.  
  101.             int tests = in.nextInt();
  102.             for (int i = 0; i < tests; i++) {
  103.                 out.print("Case #" + (i + 1) + ": ");
  104.                 solve();
  105.             }
  106.  
  107.             out.close();
  108.         } catch (IOException e) {
  109.             e.printStackTrace();
  110.         }
  111.     }
  112.  
  113.     class FastScanner {
  114.         BufferedReader br;
  115.         StringTokenizer st;
  116.  
  117.         FastScanner(File f) {
  118.             try {
  119.                 br = new BufferedReader(new FileReader(f));
  120.             } catch (FileNotFoundException e) {
  121.                 e.printStackTrace();
  122.             }
  123.         }
  124.  
  125.         String next() {
  126.             while (st == null || !st.hasMoreTokens()) {
  127.                 try {
  128.                     st = new StringTokenizer(br.readLine());
  129.                 } catch (IOException e) {
  130.                     e.printStackTrace();
  131.                 }
  132.             }
  133.             return st.nextToken();
  134.         }
  135.  
  136.         int nextInt() {
  137.             return Integer.parseInt(next());
  138.         }
  139.  
  140.         long nextLong() {
  141.             return Long.parseLong(next());
  142.         }
  143.  
  144.         double nextDouble() {
  145.             return Double.parseDouble(next());
  146.         }
  147.     }
  148.  
  149.     public static void main(String[] arg) {
  150.         new B().run();
  151.     }
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement