poj1408 Fishnet

发表于 | 更新于

Link

Solution

简单的枚举

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=30+10;
typedef double ld;
const ld eps=1e-10;
using std::vector;
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> inline T sqr(T a){return a*a;}
template <class T> inline T abs(T x){return x>0?x:-x;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
};
typedef vec point;
typedef vector<point> poly;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld b){return vec(a.x*b,a.y*b);}
vec operator /(vec a,ld b){return vec(a.x/b,a.y/b);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
/*ld size(const poly& p)
{
	ld res=0;
	int n=p.size();
	for(int i=0;i<n;i++)
		res+=outer(p[i]-p[0],p[(i+1)%n]-p[0]);
	assert(res>=0);
	return res/2;
}*/
ld size(point A,point B,point C,point D){return (abs(outer(B-A,C-A))+abs(outer(C-A,D-A)))/2;}
struct line
{
	point A;vec v;
	line(point _A,vec _v):A(_A),v(_v){}
};
point cross(line l,line r)
{
	vec v=l.A-r.A;
	ld t=outer(v,r.v)/outer(r.v,l.v);
	return l.A+l.v*t;
}
void WORK(int n)
{
	static ld a[MAXN],b[MAXN],c[MAXN],d[MAXN];
	static point mat[MAXN][MAXN];
	for(int i=1;i<=n;i++) fred(a[i]);
	for(int i=1;i<=n;i++) fred(b[i]);
	for(int i=1;i<=n;i++) fred(c[i]);
	for(int i=1;i<=n;i++) fred(d[i]);
	a[n+1]=b[n+1]=c[n+1]=d[n+1]=1;
	for(int hor=0;hor<=n+1;hor++)
	{
		line ho=line(point(0,c[hor]),point(1,d[hor])-point(0,c[hor]));
		for(int ver=0;ver<=n+1;ver++)
		{
			line ve=line(point(a[ver],0),point(b[ver],1)-point(a[ver],0));
			mat[hor][ver]=cross(ho,ve);
		}
	}
	ld ANS=-1;
	for(int hor=0;hor<=n;hor++)
		for(int ver=0;ver<=n;ver++)
			chkmx(ANS,size(mat[hor][ver],mat[hor+1][ver],mat[hor+1][ver+1],mat[hor][ver+1]));
	printf("%.6f\n",ANS);
}
int main()
{
	freopen("input","r",stdin);	
	int n;while(red(n) && n) WORK(n);	
	return 0;
}