Aizu Online Judge 1133 Water Tank

■1133 Water Tank

実装ゲー．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import javax.swing.*;  
7. import java.awt.*;  
8.   
9. import static java.lang.Math.*;  
10. import static java.util.Arrays.*;  
11.   
12. // AC  
13. public class Main{  
14.   
15.  Scanner sc=new Scanner(System.in);  
16.   
17.  int INF=1<<28;  
18.  double EPS=1e-6;  
19.   
20.  int d;  
21.  int n;  
22.  int[] x, h;  
23.  int m;  
24.  int[] f, dv;  
25.  int l;  
26.  int[] p, t;  
27.   
28.  void run(){  
29.   d=sc.nextInt();  
30.   for(int k=0; k<d; k++){  
31.    n=sc.nextInt()+1;  
32.    x=new int[n+1];  
33.    h=new int[n+1];  
34.    x[0]=0;  
35.    x[n]=100;  
36.    h[0]=h[n]=50;  
37.    for(int i=1; i<n; i++){  
38.     x[i]=sc.nextInt();  
39.     h[i]=sc.nextInt();  
40.    }  
41.    m=sc.nextInt();  
42.    f=new int[m];  
43.    dv=new int[m];  
44.    for(int i=0; i<m; i++){  
45.     f[i]=sc.nextInt();  
46.     dv[i]=sc.nextInt();  
47.    }  
48.    l=sc.nextInt();  
49.    p=new int[l];  
50.    t=new int[l];  
51.    for(int i=0; i<l; i++){  
52.     p[i]=sc.nextInt();  
53.     t[i]=sc.nextInt();  
54.    }  
55.    solve();  
56.   }  
57.  }  
58.   
59.  double[] y, a;  
60.  double time;  
61.   
62.  void solve(){  
63.   y=new double[n];  
64.   a=new double[n];  
65.   for(int j=0; j<m; j++){  
66.    for(int i=0; i<n; i++){  
67.     if(x[i]<f[j]&&f[j]<x[i+1]){  
68.      a[i]+=dv[j]/30.0;  
69.     }  
70.    }  
71.   }  
72.   // Visualizer v=new Visualizer();  
73.   
74.   double[] ans=new double[l];  
75.   fill(ans, -1);  
76.   
77.   for(time=0;;){  
78.    double min=INF;  
79.    for(int i=0; i<n; i++){  
80.     if(a[i]>EPS){  
81.      if(y[i]+EPS<h[i]){  
82.       min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);  
83.      }  
84.      if(y[i]+EPS<h[i+1]){  
85.       min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);  
86.      }  
87.     }  
88.    }  
89.    if(min==INF){  
90.     for(;;);  
91.    }  
92.    for(int j=0; j<l; j++){  
93.     if(time<t[j]+EPS&&t[j]+EPS<time+min){  
94.      for(int i=0; i<n; i++){  
95.       if(x[i]<p[j]&&p[j]<x[i+1]){  
96.        ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);  
97.       }  
98.      }  
99.     }  
100.    }  
101.    boolean all50=true;  
102.    time+=min;  
103.    for(int i=0; i<n; i++){  
104.     y[i]+=min*a[i]/(x[i+1]-x[i]);  
105.     all50&=abs(y[i]-50)<EPS;  
106.    }  
107.    // v.repaint();  
108.    // sleep(1000);  
109.   
110.    if(all50){  
111.     break;  
112.    }  
113.    double[] a2=new double[n];  
114.   
115.    for(int j=0; j<n; j++){  
116.     boolean[] bottom=new boolean[n];  
117.     int left, right;  
118.     for(left=j; left>=0&&y[left]+EPS>h[left]; left--);  
119.     for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);  
120.   
121.     if(y[left]+EPS<y[j]){  
122.      for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){  
123.       bottom[i]=true;  
124.      }  
125.     }  
126.     if(y[right]+EPS<y[j]){  
127.      for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){  
128.       bottom[i]=true;  
129.      }  
130.     }  
131.     if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){  
132.      for(int i=left; i<=right; i++){  
133.       bottom[i]=true;  
134.      }  
135.     }  
136.     int sum=0;  
137.     for(int i=0; i<n; i++){  
138.      if(bottom[i]){  
139.       sum+=x[i+1]-x[i];  
140.      }  
141.     }  
142.     for(int i=0; i<n; i++){  
143.      if(bottom[i]){  
144.       a2[i]+=a[j]/sum*(x[i+1]-x[i]);  
145.      }  
146.     }  
147.    }  
148.    a=a2.clone();  
149.   }  
150.   for(int i=0; i<l; i++){  
151.    println(ans[i]+EPS<0?"50.0":ans[i]+"");  
152.   }  
153.  }  
154.   
155.  void sleep(long millis){  
156.   try{  
157.    Thread.sleep(millis);  
158.   }catch(InterruptedException e){  
159.    e.printStackTrace();  
160.   }  
161.  }  
162.   
163.  void debug(Object... os){  
164.   // System.err.println(Arrays.deepToString(os));  
165.  }  
166.   
167.  void print(String s){  
168.   System.out.print(s);  
169.  }  
170.   
171.  void println(String s){  
172.   System.out.println(s);  
173.  }  
174.   
175.  public static void main(String[] args){  
176.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
177.   new Main().run();  
178.  }  
179.   
180.  public class Visualizer extends JFrame{  
181.   Visualizer(){  
182.    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);  
183.    setVisible(true);  
184.    getContentPane().add(new MainPanel(), BorderLayout.CENTER);  
185.    pack();  
186.   }  
187.   
188.   class MainPanel extends JPanel{  
189.    MainPanel(){  
190.     setPreferredSize(new Dimension(512, 512));  
191.    }  
192.   
193.    public void paintComponent(Graphics g){  
194.     int width=getWidth();  
195.     int height=getHeight();  
196.     for(int i=0; i<n; i++){  
197.      g.setColor(Color.BLUE);  
198.      g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,  
199.        (int)(y[i]*4));  
200.      g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);  
201.     }  
202.   
203.     for(int i=0; i<=n; i++){  
204.      g.setColor(Color.RED);  
205.      g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);  
206.     }  
207.   
208.     g.setColor(Color.BLACK);  
209.     g.drawString(""+time, 100, 100);  
210.    }  
211.   }  
212.  }  
213. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import javax.swing.*;
import java.awt.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-6;

 int d;
 int n;
 int[] x, h;
 int m;
 int[] f, dv;
 int l;
 int[] p, t;

 void run(){
  d=sc.nextInt();
  for(int k=0; k<d; k++){
   n=sc.nextInt()+1;
   x=new int[n+1];
   h=new int[n+1];
   x[0]=0;
   x[n]=100;
   h[0]=h[n]=50;
   for(int i=1; i<n; i++){
    x[i]=sc.nextInt();
    h[i]=sc.nextInt();
   }
   m=sc.nextInt();
   f=new int[m];
   dv=new int[m];
   for(int i=0; i<m; i++){
    f[i]=sc.nextInt();
    dv[i]=sc.nextInt();
   }
   l=sc.nextInt();
   p=new int[l];
   t=new int[l];
   for(int i=0; i<l; i++){
    p[i]=sc.nextInt();
    t[i]=sc.nextInt();
   }
   solve();
  }
 }

 double[] y, a;
 double time;

 void solve(){
  y=new double[n];
  a=new double[n];
  for(int j=0; j<m; j++){
   for(int i=0; i<n; i++){
    if(x[i]<f[j]&&f[j]<x[i+1]){
     a[i]+=dv[j]/30.0;
    }
   }
  }
  // Visualizer v=new Visualizer();

  double[] ans=new double[l];
  fill(ans, -1);

  for(time=0;;){
   double min=INF;
   for(int i=0; i<n; i++){
    if(a[i]>EPS){
     if(y[i]+EPS<h[i]){
      min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);
     }
     if(y[i]+EPS<h[i+1]){
      min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);
     }
    }
   }
   if(min==INF){
    for(;;);
   }
   for(int j=0; j<l; j++){
    if(time<t[j]+EPS&&t[j]+EPS<time+min){
     for(int i=0; i<n; i++){
      if(x[i]<p[j]&&p[j]<x[i+1]){
       ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);
      }
     }
    }
   }
   boolean all50=true;
   time+=min;
   for(int i=0; i<n; i++){
    y[i]+=min*a[i]/(x[i+1]-x[i]);
    all50&=abs(y[i]-50)<EPS;
   }
   // v.repaint();
   // sleep(1000);

   if(all50){
    break;
   }
   double[] a2=new double[n];

   for(int j=0; j<n; j++){
    boolean[] bottom=new boolean[n];
    int left, right;
    for(left=j; left>=0&&y[left]+EPS>h[left]; left--);
    for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);

    if(y[left]+EPS<y[j]){
     for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){
      bottom[i]=true;
     }
    }
    if(y[right]+EPS<y[j]){
     for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){
      bottom[i]=true;
     }
    }
    if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){
     for(int i=left; i<=right; i++){
      bottom[i]=true;
     }
    }
    int sum=0;
    for(int i=0; i<n; i++){
     if(bottom[i]){
      sum+=x[i+1]-x[i];
     }
    }
    for(int i=0; i<n; i++){
     if(bottom[i]){
      a2[i]+=a[j]/sum*(x[i+1]-x[i]);
     }
    }
   }
   a=a2.clone();
  }
  for(int i=0; i<l; i++){
   println(ans[i]+EPS<0?"50.0":ans[i]+"");
  }
 }

 void sleep(long millis){
  try{
   Thread.sleep(millis);
  }catch(InterruptedException e){
   e.printStackTrace();
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }

 public class Visualizer extends JFrame{
  Visualizer(){
   setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   setVisible(true);
   getContentPane().add(new MainPanel(), BorderLayout.CENTER);
   pack();
  }

  class MainPanel extends JPanel{
   MainPanel(){
    setPreferredSize(new Dimension(512, 512));
   }

   public void paintComponent(Graphics g){
    int width=getWidth();
    int height=getHeight();
    for(int i=0; i<n; i++){
     g.setColor(Color.BLUE);
     g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,
       (int)(y[i]*4));
     g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);
    }

    for(int i=0; i<=n; i++){
     g.setColor(Color.RED);
     g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);
    }

    g.setColor(Color.BLACK);
    g.drawString(""+time, 100, 100);
   }
  }
 }
}