Aizu Online Judge 1226 Fishnet

■1226 Fishnet

全通り試す．面積はヘロンの公式を使えば簡単．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  P[] a, b, c, d;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    if(n==0){  
23.     break;  
24.    }  
25.    n+=2;  
26.    a=new P[n];  
27.    b=new P[n];  
28.    c=new P[n];  
29.    d=new P[n];  
30.    a[0]=new P(0, 0);  
31.    b[0]=new P(0, 1);  
32.    c[0]=new P(0, 0);  
33.    d[0]=new P(1, 0);  
34.    for(int i=1; i<n-1; i++)  
35.     a[i]=new P(sc.nextDouble(), 0);  
36.    for(int i=1; i<n-1; i++)  
37.     b[i]=new P(sc.nextDouble(), 1);  
38.    for(int i=1; i<n-1; i++)  
39.     c[i]=new P(0, sc.nextDouble());  
40.    for(int i=1; i<n-1; i++)  
41.     d[i]=new P(1, sc.nextDouble());  
42.    a[n-1]=new P(1, 0);  
43.    b[n-1]=new P(1, 1);  
44.    c[n-1]=new P(0, 1);  
45.    d[n-1]=new P(1, 1);  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   double ans=0;  
52.   for(int j=0; j<n-1; j++){  
53.    for(int i=0; i<n-1; i++){  
54.     P p1=isLL(a[i], b[i], c[j], d[j]);  
55.     P p2=isLL(a[i+1], b[i+1], c[j], d[j]);  
56.     P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);  
57.     P p4=isLL(a[i], b[i], c[j+1], d[j+1]);  
58.     ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));  
59.    }  
60.   }  
61.   println(String.format("%.6f", ans+EPS));  
62.  }  
63.   
64.  double area(P p1, P p2, P p3){  
65.   double a=p1.sub(p2).abs();  
66.   double b=p2.sub(p3).abs();  
67.   double c=p3.sub(p1).abs();  
68.   double s=(a+b+c)/2;  
69.   return Math.sqrt(s*(s-a)*(s-b)*(s-c));  
70.  }  
71.   
72.  // 直線と直線の交点  
73.  P isLL(P p1, P p2, P q1, P q2){  
74.   double d=q2.sub(q1).det(p2.sub(p1));  
75.   if(abs(d)<EPS)  
76.    return null;  
77.   return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));  
78.  }  
79.   
80.  class P{  
81.   double x, y;  
82.   
83.   P(){  
84.    this(0, 0);  
85.   }  
86.   
87.   P(double x, double y){  
88.    this.x=x;  
89.    this.y=y;  
90.   }  
91.   
92.   P add(P p){  
93.    return new P(x+p.x, y+p.y);  
94.   }  
95.   
96.   P sub(P p){  
97.    return new P(x-p.x, y-p.y);  
98.   }  
99.   
100.   P mul(double m){  
101.    return new P(x*m, y*m);  
102.   }  
103.   
104.   P div(double d){  
105.    return new P(x/d, y/d);  
106.   }  
107.   
108.   double abs(){  
109.    return Math.sqrt(abs2());  
110.   }  
111.   
112.   double abs2(){  
113.    return x*x+y*y;  
114.   }  
115.   
116.   double arg(){  
117.    return Math.atan2(y, x);  
118.   }  
119.   
120.   // inner product  
121.   double dot(P p){  
122.    return x*p.x+y*p.y;  
123.   }  
124.   
125.   // outer product  
126.   double det(P p){  
127.    return x*p.y-y*p.x;  
128.   }  
129.   
130.   P rot90(){  
131.    return new P(-y, x);  
132.   }  
133.   
134.   // conjugation  
135.   P conj(){  
136.    return new P(x, -y);  
137.   }  
138.   
139.   @Override  
140.   public String toString(){  
141.    return "("+x+", "+y+")";  
142.   }  
143.  }  
144.   
145.  void debug(Object... os){  
146.   System.err.println(Arrays.deepToString(os));  
147.  }  
148.   
149.  void print(String s){  
150.   System.out.print(s);  
151.  }  
152.   
153.  void println(String s){  
154.   System.out.println(s);  
155.  }  
156.   
157.  public static void main(String[] args){  
158.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
159.   new Main().run();  
160.  }  
161. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 P[] a, b, c, d;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   n+=2;
   a=new P[n];
   b=new P[n];
   c=new P[n];
   d=new P[n];
   a[0]=new P(0, 0);
   b[0]=new P(0, 1);
   c[0]=new P(0, 0);
   d[0]=new P(1, 0);
   for(int i=1; i<n-1; i++)
    a[i]=new P(sc.nextDouble(), 0);
   for(int i=1; i<n-1; i++)
    b[i]=new P(sc.nextDouble(), 1);
   for(int i=1; i<n-1; i++)
    c[i]=new P(0, sc.nextDouble());
   for(int i=1; i<n-1; i++)
    d[i]=new P(1, sc.nextDouble());
   a[n-1]=new P(1, 0);
   b[n-1]=new P(1, 1);
   c[n-1]=new P(0, 1);
   d[n-1]=new P(1, 1);
   solve();
  }
 }

 void solve(){
  double ans=0;
  for(int j=0; j<n-1; j++){
   for(int i=0; i<n-1; i++){
    P p1=isLL(a[i], b[i], c[j], d[j]);
    P p2=isLL(a[i+1], b[i+1], c[j], d[j]);
    P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);
    P p4=isLL(a[i], b[i], c[j+1], d[j+1]);
    ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));
   }
  }
  println(String.format("%.6f", ans+EPS));
 }

 double area(P p1, P p2, P p3){
  double a=p1.sub(p2).abs();
  double b=p2.sub(p3).abs();
  double c=p3.sub(p1).abs();
  double s=(a+b+c)/2;
  return Math.sqrt(s*(s-a)*(s-b)*(s-c));
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }

  @Override
  public String toString(){
   return "("+x+", "+y+")";
  }
 }

 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();
 }
}