不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

一道竞赛题 (Winter Camp 2002)

楼主aliceZOOZ（alice）2002-02-18 21:22:19 在专题开发/技术/项目 / 数据结构与算法提问

奶牛浴场
happy.exe

【问题描述】
由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。

【输入文件】
输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0<x<L，0<y<W。

【输出文件】
输出文件仅一行，包含一个整数S，表示浴场的最大面积。

【输入输出样例】
happy.in
10 10
4
1 1
9 1
1 9
9 9

happy.out
80

【参数约定】
0<n<5000
1<L,W<30000
问题点数：100、回复次数：89Top

1 楼starfish（海星）回复于 2002-02-18 21:52:15 得分 0

这个题目应该不难吧,根据题意搜索就可以了……
USACO的题目每年都拿奶牛开刷，真难为奶牛了～～Top

2 楼aliceZOOZ（alice）回复于 2002-02-18 23:52:55 得分 0

当然，要考虑到算法的时间复杂度Top

3 楼Chice_wxg（学)(习）回复于 2002-02-19 08:58:52 得分 0

晕，想想。Top

4 楼wangqiqi（polymath）回复于 2002-02-19 11:44:57 得分 1

复杂度 n^2，不算大。Top

5 楼aliceZOOZ（alice）回复于 2002-02-19 11:46:38 得分 0

O(n^2)是不大，但具体应该怎么做呢？Top

6 楼ritchiex（hxx）回复于 2002-02-19 15:39:15 得分 0

用动态规划解决，时间复杂度是n^2.Top

7 楼aliceZOOZ（alice）回复于 2002-02-19 16:16:20 得分 0

有人能给出具体的算法描述或程序吗？
要求时间复杂度为O(n^2)的。
Top

8 楼aliceZOOZ（alice）回复于 2002-02-20 08:24:34 得分 0

没人知道吗？Top

9 楼dongmen（东门吹气）回复于 2002-02-20 12:51:08 得分 0

不会吧？n^2？hmmm
内存和时限多少？Top

10 楼dongmen（东门吹气）回复于 2002-02-20 13:16:02 得分 2

hehe 总算会点了，我真笨阿，还要从大家的n^2来获得提示：（

设浴场左上右下两个点：a,b

则这两个点肯定在产奶点上，或者在边上，而且浴场里不含产奶点，但是边上可以含。
这样设想就多了5000个点（边界上的）。。好像是10000，唉，反正我也不管了（我也是千百个不愿意阿），等等。。不是全部的，一条边界最多再多3000个点（横坐标上有产奶点，边界上才再加）。
把点排序（xixi，复杂度忘了）
然后从左上角开始，确定A点，然后搜B点，从(Xa+1,Ya+1）行开始搜吧(可以搜到每行的边界)。。然后一行搜完把x最小的那个记下来，下一行就不能搜超过那x值的点了（浴场围到产奶点了），本行的相互没影响（产奶点可以在边上）；然后A点换，hehe，继续，复杂度嘛比n^2少点吧，i hope，不过n被加了，最多可能有。。6000吧，xixi，砍！hehe，自由发挥吧

对了有无测试数据？Top

11 楼dongmen（东门吹气）回复于 2002-02-20 13:18:34 得分 0

没有n^2..
是1+2+...+n吧？只搜索排序后在A后面的B点Top

12 楼mathe（）回复于 2002-02-20 14:21:07 得分 20

浴场的左上和右下两个点一般来说不会是产奶点，倒是浴场的四条边上都必然产奶点。可以通过枚举左边和右边上的产奶点对，然后搜索每个产奶点对下最大的浴场。这种算法的时间复杂度肯定小于n^3，但很难保证小于n^2。不过在搜索过程中，可以通过很多方法先过滤很多情况。比如两个产奶点组成的矩形内部还包含其他产奶点，那么我们就不需要搜索这两个点对了。最终的时间复杂度应该是稍微大于n^2.Top

13 楼aliceZOOZ（alice）回复于 2002-02-20 14:21:22 得分 0

"则这两个点肯定在产奶点上，或者在边上"
如果
---------
|.......|
|...*...|
|.......|
|.*...*.|
|.......|
|...*...|
|.......|
---------

解答是
---------
|.......|
|.AAAAA.|
|.A...A.|
|.A...A.|
|.A...A.|
|.AAAAA.|
|.......|
---------
Top

14 楼aliceZOOZ（alice）回复于 2002-02-20 14:23:10 得分 0

把上面的图（文字）复制，然后在记事本中粘贴，就可以看到原始效果。
Top

15 楼aliceZOOZ（alice）回复于 2002-02-20 14:26:37 得分 0

to dongmen(东门吹气)：mathe说了我想要说的。内存和时限分别是1M和5s(P933)。有测试数据。时间复杂度必须降到O(n^2)。
Top

16 楼natureshuo（）回复于 2002-02-20 17:00:31 得分 0

attentionTop

17 楼dongmen（东门吹气）回复于 2002-02-20 18:19:12 得分 0

Oh
hehe sorry 错了，果然还没懂，xixiTop

18 楼Zig（Zig）回复于 2002-02-20 20:51:20 得分 30

1. 这不是usaco
2. O(n^2)可以过
3. O(n^3)也可以过（这是标程的写法）
4. 有人有更好的吗？Top

19 楼aliceZOOZ（alice）回复于 2002-02-20 21:03:44 得分 0

to Zig(Zig): 看来遇到高人了，能贴一下O(n^3)的标程吗？我想了一个O(n^2)的方法，在P667上最慢的要1s。真想不通O(n^3)如何出解。
Top

20 楼dongmen（东门吹气）回复于 2002-02-21 21:15:47 得分 0

up
居然还没解答。。Top

21 楼Zig（Zig）回复于 2002-02-22 19:22:10 得分 0

据称是剪枝，就是遇到不可能更大的就剪掉就可以了。
当然，只是据称。标程没有。
不过还有复杂度更低的吗？
你既然拿到题目了，还不会解法？！Top

22 楼aliceZOOZ（alice）回复于 2002-02-23 12:09:46 得分 0

to Zig: 拿到题目就会解法？这是哪门子的逻辑！你有什么好的剪枝，说出来听听。Top

23 楼IT_worker（IT工人）回复于 2002-02-23 15:18:12 得分 2

//复杂度应该不会太大
//不知道能否测试一下
#include "stdafx.h"
#include <memory.h>
#include<algorithm>
#include<fstream.h>

struct rect
{
int min_x,min_y,max_x,max_y;
rect *child;
rect(){memset(this,0,sizeof(*this));}
~rect(){delete [] child;}

void add(long x,long y)
{
if(x<=min_x || x>=max_x || y<=min_y || y>=max_y)
return;
if(child)
{
child[0].add(x,y);
child[1].add(x,y);
child[2].add(x,y);
child[3].add(x,y);
return ;
}
rect *p = new rect[4];
memcpy(p,this,sizeof(*this));
memcpy(p+1,this,sizeof(*this));
memcpy(p+2,this,sizeof(*this));
memcpy(p+3,this,sizeof(*this));
p[0].max_x = x;
p[1].min_x = x;
p[2].max_y = y;
p[3].min_y = y;
child = p;
}

double area()
{
if(child)
{
double a[4];
a[0] = child[0].area();
a[1] = child[1].area();
a[2] = child[2].area();
a[3] = child[2].area();
return *std::max_element(a,a+4);
}
return double(max_x-min_x)*(max_y-min_y);
}
};

int main(int argc, char* argv[])
{
fstream fin(argv[1],ios::in);
long x,y,i;
rect r;
fin>>r.max_x>>r.max_y>>i;
for(;i--;)
{
fin>>x>>y;
r.add(x,y);
}
cout<<endl<<r.area();
return 0;
}
Top

24 楼aliceZOOZ（alice）回复于 2002-02-23 16:31:26 得分 0

to IT_worker(IT工人)：很不好意思的告诉你，你程序的速度太慢了。连O(n^4)的算法都不如，你的算法该不会是O(4^n)的复杂度吧！
http://61.136.0.239/oibh/download/wintercamp/wintercamp2002.zip
http://61.136.0.239/oibh/download/wintercamp/wintercamp2002testdata.zip
有题目和测试数据下载。Top

25 楼aliceZOOZ（alice）回复于 2002-02-23 16:36:18 得分 0

加分了，希望大家踊跃讨论Top

26 楼IT_worker（IT工人）回复于 2002-02-24 11:11:13 得分 0

//上面我给出的算法确实太烂了，复杂度是O(2^n)
//下面这个复杂度为：n^3。
//将fzn改为由multiset<long>派生可以使得复杂度变为O(n*n*log(n))

#include "stdafx.h"
#include <fstream.h>
#include <windows.h>
#include <algorithm>
#include <vector>

using namespace std;

struct fzn : public vector<long>
{
long m_r;
long radius()
{
long *i=begin(),n = size();
for(m_r=0 ;--n;)
m_r = _cpp_max(m_r,i[1]-i[0]);
return m_r;
}

long remove(long x)
{
long *i = upper_bound(begin(),end(),x)-1;
m_r = _cpp_max(m_r,i[1]-i[-1]);
//下面一句的复杂度为n
//如果将使得此函数复杂度为log(n)
erase(i);
return m_r;
}
};

//求出所有x方向起点为p[0].x终点为p[i].x(0<i<=n)的矩形的面积的最大值
//复杂度：O(n*n)
double area(fzn y,POINT *p,long n)
{
double a,w,h;
w = p[n].x-p[0].x;
h = y.radius();
a = w*h;
for(;--n;)
{
w = p[n].x-p[0].x;
h = y.remove(p[n].y);
a = _cpp_max(a,w*h);
}
return a;
}

bool cmp(POINT a,POINT b)
{
return a.x==b.x? a.y<b.y:a.x<b.x;
}

//复杂度：O(n^3)
double Area(POINT*p,long n,long w,long h)
{
fzn F;
F.push_back(0);
for(long i=0; i<n; i++)
F.push_back(p[i].y);
F.push_back(h);
sort(F.begin(),F.end());

p[n].x = p[n].y = 0;
p[++n].x = w; p[n].y = h;
sort(p,p+n+1,cmp);

double a,A = area(F,p,n);
for(i=1; i<n; i++)
{
F.remove(p[i].y);
a = area(F,p+i,n-i);
if(a>A) A = a;
if(i%100==0) cout<<i<<endl;
}
return A;
}

int main(int argc, char* argv[])
{
::fstream fin(argv[1],ios::in);
long n,i,w,h;
POINT *p;

fin>>w>>h>>n;

p = new POINT[n+2];

for(i=n;i--;)
fin>>p[i].x>>p[i].y;

cout<<Area(p,n,w,h);

delete [] p;
return 0;
}Top

27 楼IT_worker（IT工人）回复于 2002-02-24 11:37:06 得分 0

to:aliceZOOZ
有O(n^2)的算法吗？贴出来让大家学习学习。我上面的程序在p4-1.5g的机器上对5000个点用了10秒，真是惭愧得很。Top

28 楼intfree（）回复于 2002-02-24 15:42:50 得分 20

TC3.0下编译通过

#include <fstream.h>
#include <stdlib.h>

const MAX = 6000;

struct Tpoint
{
int x, y;
};

Tpoint d[MAX];
int n, dd[MAX];

int sort_x(const void * a, const void * b)
{
return ((Tpoint *) a) -> x - ((Tpoint *) b) -> x;
}

int sort_y(const void * a, const void * b)
{
return d[* (int *) a].y - d[* (int *) b].y;
}

void main()
{
ifstream inp("happy.in");
ofstream out("happy.out");
int ww, hh, i, j, pred[MAX], succ[MAX];
long max = 0;
inp >> ww >> hh >> n;
for (i = 0; i < n; i ++)
{
inp >> d[i].x >> d[i].y;
}
d[n].x = d[n].y = d[n + 1].x = d[n + 1].y = 0;
d[n + 2].x = d[n + 3].x = ww;
d[n + 2].y = d[n + 3].y = hh;
for (i = 0, n += 3; i < n; i ++)
{
dd[i] = i;
}
qsort(d, n, sizeof(d[0]), sort_x);
qsort(dd, n, sizeof(dd[0]), sort_y);
for (i = 1; i < n; i ++)
if (d[i].x != d[i + 1].x)
{
int h, last = 0, mh = 0;
long s;
for (j = 1; j < n; j ++)
if (dd[j] > i)
{
mh = ((h = d[dd[j]].y - d[last].y) > mh) ? h : mh;
pred[dd[j]] = last;
succ[last] = dd[j];
last = dd[j];
}
succ[last] = n;
max = ((s = (long) mh * (ww - d[i].x)) > max) ? s : max;
for (j = n - 1; j > i; j --)
{
pred[succ[j]] = pred[j];
succ[pred[j]] = succ[j];
if ((h = d[succ[j]].y - d[pred[j]].y) > mh)
{
max = ((s = (long) (mh = h) * (d[j].x - d[i].x)) > max) ? s : max;
}
}
}
out << max << endl;
}Top

29 楼bluetooth_2001（热情的沙漠）回复于 2002-02-24 19:25:33 得分 0

看看Top

30 楼cxjddd（又是花开时）回复于 2002-02-25 22:28:22 得分 0

试试看。Top

31 楼h8135（tiger0）回复于 2002-02-27 08:34:11 得分 5

好象用递归方法也可以求解

f(rect,n) 等于
1、如果n == 0，返回rect;
2、如果n > 1，求rc = f(rect,n - 1),如果(Xn,Yn)在rc之外(包括边界)，则返回rect；如果(Xn,Yn)在rc之内,则以x = Xn为边界，将牧场分为两部分，
分别求两边最大的浴场f(leftrect,i),f(rightrect,j),i + j < n;同样以y = Yn为边界，求上下两部分的最大浴场,返回这四个浴场中最大的那个即可。

Top

32 楼aliceZOOZ（alice）回复于 2002-02-27 21:57:13 得分 0

to h8135(tiger0)：4种可能：1.我没看懂；2.你没说清；3.时间复杂度太高；4.算法错误。
to intfree()：这个算法是O(n^2)的。
to intfree() & Zig(Zig)：我希望得到，向Zig说的那样，更低复杂度的算法，或者O(n^3)+剪枝可以出解的方法。
Top

33 楼xf8zbf（瞎想）回复于 2002-02-28 11:53:24 得分 2

看我的
//如在边界上，则定义为此边上有点

//如此总的来说必有以下两种情况之一
// 1.左右两边上有点
// 2.上下两边上有点
int N; //点个数
POINT point[5000+4];//点
int I0,J0; //宽高
long areaMax; //面积

{
areaMax=I0>J0 ? I0:J0;
for(n=0;n<N;n++)
{
pointA=point[n];
//如MAX N小于MAX I0或J0，也可不用此循环，改用N，
//此时调用成（pointA.x,pointB.x,pointA.y)即可
//不过还要增加角部四个点N=N+4
for(i=0;i<I0;i++)
{
//此点必在左或右边时的最大值
if(pointA.x<i)
area1=Get_H_Maxarea(pointA.x,i,pointA.y);
else
area1=Get_H_Maxarea(i,pointA.x,pointA.y);
完成比较替换记录;
}
pointB.x=pointA.x;
for(j=0;j<J0;j++)
{
//此点必在上或下两边时的最大值（工字只是意会一下）
if(pointA.y<j)
area2=Get工Maxarea(pointA.y,j,pointA.x);
else
area2=Get工Maxarea(j,pointA.y,pointA.x);
完成比较替换记录;
}
}
}
//纵可达边界最大值
Get_H_Maxarea(int XA,int XB,int Y0)
{
ASSERT(XB>=XA);
if(XA==XB) return 0;
if(XB-XA==1) return J0;

float DY=(areaMax+0.0f)/(XB-XA+0.0f);
int Y1=0,Y2=J0;
int X,Y;
for(n=0;n<N;n++)
{
X=point[n].x, Y=point[n].y;
if(X<=XA || X>=XB)
continue;
if(Y<=Y0 && Y>Y1) Y1=Y;
if(Y>=Y0 && Y<Y2) Y2=Y;
if(Y2-Y1<DY) return 0;//可以加快循环
}
return (XB-XA)*(Y2-Y1);
}
//横可达边界最大值
Get工Maxarea(int YA,int YB,int X0)
{
道理同上;
}
Top

34 楼aliceZOOZ（alice）回复于 2002-02-28 17:51:19 得分 0

to xf8zbf(瞎想) ：你的算法是O(n^3)的复杂度吧，可能还不止呢。一般情况下，O(n^3)的算法会超时，但不排除有好剪枝的可能性。你可以自己测试一下。题目和数据可以到

http://61.136.0.239/oibh/download/wintercamp/wintercamp2002.zip
http://61.136.0.239/oibh/download/wintercamp/wintercamp2002testdata.zip

下载。Top

35 楼aliceZOOZ（alice）回复于 2002-02-28 23:27:54 得分 0

一不小心，点了移动贴子，无缘无故扣了信誉分Top

36 楼h8135（tiger0）回复于 2002-03-02 08:50:31 得分 0

看不到昨天的答复？Top

37 楼RedGuest（Haha）回复于 2002-03-02 11:10:28 得分 2

大伙能不能先描述一下算法，程序好难看！！！！！！！！！
我的想法：
假设有n头奶牛，则可以将养牛场分为n^2个小矩形。现在对小矩形进行扩充,即延长小矩形的边至下一个点。从左上角的小矩形开始，可以朝x方向（向右）扩充，或朝y方向（向下）扩充，或者两个方向都扩（有的可以，有的不能两个方向扩充），这样，从最多三个扩充的矩形面积中找出最大的一个。同时可以注意到，已经扩充的相临矩形的一些状态信息可以作为目前矩形是否扩充，或者怎样扩充的依据，例如，1.没有任何边与养牛场边缘重合的小矩形（或者叫内部小矩形）只能进行两个方向同时扩充 2.两个方向扩充时，一般只能各扩充一格，除非邻点在同一直线上。
这样，复杂度应该是n^2上了
Top

38 楼h8135（tiger0）回复于 2002-03-02 12:41:33 得分 0

昨天贴的源码，怎么看不到？下面是算法描述，时间复杂度应该在O(n^2)内，happy5.ans是错误的吧？
/*
一种算法，速度很快。
思想：以某点为坐标原点，将牧场分为四个象限，查找如下的点：
1）第1象限，x递增，Y递增
2）第4象限，x递增，Y递减
3）第2象限，x递减，Y递增
4）第3象限，x递减，Y递减
在每个象限做如下操作：
取相邻两点和原点决定的三条边，在相邻象限内查找最远的第四条边，得到最大矩形区域。
还需考虑到与当前点同x,同y的点的限制
*/

Top

39 楼aliceZOOZ（alice）回复于 2002-03-02 14:36:28 得分 0

happy5.in/happy5.ans绝对正确，
你可以编写一个简单的，O(n^3)的算法来验算。
我想一定是你的算法/程序错了。
Top

40 楼h8135（tiger0）回复于 2002-03-02 16:57:16 得分 0

看一看,happy5的矩形区域是左上角是(0,2496),宽2500。高5004，面积12510000：
#include <algorithm>
using namespace std;
#include <fstream.h>

struct position
{
int x,y;
bool operator!=(const position& pos) {return x != pos.x || y != pos.y;};
};

struct rect
{
int left,top,width,height;
int right() { return left + width;};
int bottom(){ return top + height;};
int area(){ return width * height; };
};

static const int MAX_SIZE = 10000;
static position pos_set_x[MAX_SIZE];
static int EN_list[MAX_SIZE]; static int EN_index = 0;
static int ES_list[MAX_SIZE]; static int ES_index = 0;
static int WN_list[MAX_SIZE]; static int WN_index = 0;
static int WS_list[MAX_SIZE]; static int WS_index = 0;
static int X_list[MAX_SIZE]; static int X_index = 0;
static int Y_list[MAX_SIZE]; static int Y_index = 0;
static int width,height;
static int num;
static position* _pos = 0;

struct compx
{
bool operator()(const position& p1,const position& p2)
{
return p1.x < p2.x;
};

};

struct compyindex
{

bool operator()(const int& p1,const int& p2)
{
return pos_set_x[p1].y < pos_set_x[p2].y;
};

};

struct compxindex
{

bool operator()(const int& p1,const int& p2)
{
return pos_set_x[p1].x < pos_set_x[p2].x;
};

};

struct comp_x
{
int max,min;

comp_x(int max,int min) {this->max = max,this->min = min;};
bool operator()(const int val){
return pos_set_x[val].x > min && pos_set_x[val].x < max;
};
};

struct comp_y
{
int max,min;

comp_y(int max,int min) {this->max = max,this->min = min;};
bool operator()(const int val){
return pos_set_x[val].y > min && pos_set_x[val].y < max;
};
};

void init_2(const char* file)
{
ifstream ins(file);
ins >> width >> height >> num;
for(int i = 0; i < num; i++) {
ins >> pos_set_x[i].x >> pos_set_x[i].y;
}

sort(pos_set_x,pos_set_x + num,compx());
}

void FindRelatedPos()
{
position& pos = *_pos;
position* ppos = find(pos_set_x,pos_set_x + num,pos);
int x_index = distance(pos_set_x,ppos);

EN_index = ES_index = WN_index = WS_index = X_index = Y_index = 0;

int fx = x_index;
int bx = fx;

for(fx++,bx--; bx > -1 || fx < num;fx++,bx--) {
if(fx < num) {
if(pos_set_x[fx].x == pos.x)
X_list[X_index++] = fx;
else if(pos_set_x[fx].y == pos.y)
Y_list[Y_index++] = fx;
else if(pos_set_x[fx].y < pos.y) {
if(EN_index == 0 || pos_set_x[fx].y > pos_set_x[EN_list[EN_index - 1]].y)
EN_list[EN_index++] = fx;
}
else {
if(ES_index == 0 || pos_set_x[fx].y < pos_set_x[ES_list[ES_index - 1]].y)
ES_list[ES_index++] = fx;
}
}

if(bx > -1){
if(pos_set_x[bx].x == pos.x)
X_list[X_index++] = bx;
else if(pos_set_x[bx].y == pos.y)
Y_list[Y_index++] = bx;
else if(pos_set_x[bx].y < pos.y) {
if(WN_index == 0 || pos_set_x[bx].y > pos_set_x[WN_list[WN_index - 1]].y)
WN_list[WN_index++] = bx;
}
else {
if(WS_index == 0 || pos_set_x[bx].y < pos_set_x[WS_list[WS_index - 1]].y)
WS_list[WS_index++] = bx;
}
}
}
sort(X_list,X_list + X_index,compyindex());
sort(Y_list,Y_list + Y_index,compxindex());
}

int findbottom_r(int right)
{
int* pint = find_if(Y_list,Y_list + Y_index,comp_x(right,_pos->x));
if(pint != Y_list + Y_index) return _pos->y;

if(ES_index == 0) return height;
for(int i = 0; i < ES_index; i++) {
if(pos_set_x[ES_list[i]].x >= right)
return i == 0 ? height : pos_set_x[ES_list[i - 1]].y;
}
return pos_set_x[ES_list[ES_index - 1]].y;
}

int findbottom_l(int left)
{
int* pint = find_if(Y_list,Y_list + Y_index,comp_x(_pos->x,left));
if(pint != Y_list + Y_index) return _pos->y;

if(WS_index == 0) return height;
for(int i = 0; i < WS_index; i++) {
if(pos_set_x[WS_list[i]].x <= left)
return i == 0 ? height : pos_set_x[WS_list[i - 1]].y;
}
return pos_set_x[WS_list[WS_index - 1]].y;
}

int findleft_t(int top)
{
int* pint = find_if(X_list,X_list + X_index,comp_y(_pos->y,top));
if(pint != X_list + X_index) return _pos->x;

if(WN_index == 0) return 0;
for(int i = 0; i < WN_index; i++) {
if(pos_set_x[WN_list[i]].y > top)
return pos_set_x[WN_list[i]].x;
}
return 0;
}

int findleft_b(int bottom)
{
int* pint = find_if(X_list,X_list + X_index,comp_y(bottom,_pos->y));
if(pint != X_list + X_index) return _pos->x;

if(WS_index == 0) return 0;
for(int i = 0; i < WS_index; i++) {
if(pos_set_x[WS_list[i]].y < bottom)
return pos_set_x[WS_list[i]].x;
}
return 0;
}

int findtop_r(int right)
{
int* pint = find_if(Y_list,Y_list + Y_index,comp_x(right,_pos->x));
if(pint != Y_list + Y_index) return _pos->y;

if(EN_index == 0) return 0;
for(int i = 0; i < EN_index; i++) {
if(pos_set_x[EN_list[i]].x >= right)
return i == 0 ? 0 : pos_set_x[EN_list[i - 1]].y;
}
return pos_set_x[EN_list[EN_index - 1]].y;
}

int findtop_l(int left)
{
int* pint = find_if(Y_list,Y_list + Y_index,comp_x(_pos->x,left));
if(pint != Y_list + Y_index) return _pos->y;

if(WN_index == 0) return 0;
for(int i = 0; i < WN_index; i++) {
if(pos_set_x[WN_list[i]].x <= left)
return i == 0 ? 0 : pos_set_x[WN_list[i - 1]].y;
}
return pos_set_x[WN_list[WN_index - 1]].y;
}

int findright_t(int top)
{
int* pint = find_if(X_list,X_list + X_index,comp_y(_pos->y,top));
if(pint != X_list + X_index) return _pos->x;

if(EN_index == 0) return width;
for(int i = 0; i < EN_index; i++) {
if(pos_set_x[EN_list[i]].y > top)
return pos_set_x[EN_list[i]].x;
}
return width;
}

int findright_b(int bottom)
{
int* pint = find_if(X_list,X_list + X_index,comp_y(bottom,_pos->y));
if(pint != X_list + X_index) return _pos->x;

if(ES_index == 0) return width;
for(int i = 0; i < ES_index; i++) {
if(pos_set_x[ES_list[i]].y < bottom)
return pos_set_x[ES_list[i]].x;
}
return width;
}

void SetMaxRect(rect& rMax,int left,int right,int top,int bottom)
{
if(rMax.area() < (right - left) * (bottom - top))
{
rMax.left = left;
rMax.top = top;
rMax.width = right - left;
rMax.height = bottom - top;
}
}

Top

41 楼h8135（tiger0）回复于 2002-03-02 16:58:52 得分 0

void ScanEN(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(EN_index == 0) {
bottom = findbottom_r(width);
SetMaxRect(rMax,pos.x,width,0,bottom);

left = findleft_t(0);
SetMaxRect(rMax,left,width,0,pos.y);
return;
}

right = pos_set_x[EN_list[0]].x;
bottom = findbottom_r(right);
SetMaxRect(rMax,pos.x,right,0,bottom);

for(int i = 0; i < EN_index - 1; i++) {
top = pos_set_x[EN_list[i]].y;
right = pos_set_x[EN_list[i + 1]].x;
bottom = findbottom_r(right);
SetMaxRect(rMax,pos.x,right,top,bottom);

left = findleft_t(top);
SetMaxRect(rMax,left,right,top,pos.y);
}

top = pos_set_x[EN_list[EN_index - 1]].y;
left = findleft_t(top);
SetMaxRect(rMax,left,width,top,pos.y);
}

void ScanES(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(ES_index == 0) {
top = findtop_r(width);
SetMaxRect(rMax,pos.x,width,top,height);

left = findleft_b(height);
SetMaxRect(rMax,left,width,pos.y,height);
return;
}

right = pos_set_x[ES_list[0]].x;
top = findtop_r(right);
SetMaxRect(rMax,pos.x,right,top,height);

for(int i = 0; i < ES_index - 1; i++) {
bottom = pos_set_x[ES_list[i]].y;
right = pos_set_x[ES_list[i + 1]].x;
top = findtop_r(right);
SetMaxRect(rMax,pos.x,right,top,bottom);

left = findleft_b(bottom);
SetMaxRect(rMax,left,right,pos.y,bottom);
}

bottom = pos_set_x[ES_list[ES_index - 1]].y;
left = findleft_b(bottom);
SetMaxRect(rMax,left,width,pos.y,bottom);
}

void ScanWN(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(WN_index == 0) {
bottom = findbottom_l(0);
SetMaxRect(rMax,0,pos.x,0,bottom);

right = findright_t(0);
SetMaxRect(rMax,0,right,0,pos.y);
return;
}

left = pos_set_x[WN_list[0]].x;
bottom = findbottom_l(left);
SetMaxRect(rMax,left,pos.x,0,bottom);

for(int i = 0; i < WN_index - 1; i++) {
top = pos_set_x[WN_list[i]].y;
left = pos_set_x[WN_list[i + 1]].x;
bottom = findbottom_l(left);
SetMaxRect(rMax,left,pos.x,top,bottom);

right = findright_t(top);
SetMaxRect(rMax,left,right,top,pos.y);
}

top = pos_set_x[WN_list[WN_index - 1]].y;
right = findright_t(top);
SetMaxRect(rMax,0,right,top,pos.y);
}

void ScanWS(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(WS_index == 0){
top = findtop_l(0);
SetMaxRect(rMax,0,pos.x,top,height);

right = findright_b(height);
SetMaxRect(rMax,0,right,pos.y,height);
return;
}

left = pos_set_x[WS_list[0]].x;
top = findtop_l(left);
SetMaxRect(rMax,left,pos.x,top,height);

for(int i = 0; i < ES_index - 1; i++) {
bottom = pos_set_x[ES_list[i]].y;
left = pos_set_x[ES_list[i + 1]].x;
top = findtop_l(left);
SetMaxRect(rMax,left,pos.x,top,bottom);

right = findright_b(bottom);
SetMaxRect(rMax,left,right,pos.y,bottom);
}

bottom = pos_set_x[WS_list[WS_index - 1]].y;
right = findright_b(bottom);
SetMaxRect(rMax,0,right,pos.y,bottom);
}

rect FindMaxArea(rect& rMax)
{
FindRelatedPos();
ScanEN(rMax);
ScanES(rMax);
ScanWN(rMax);
ScanWS(rMax);
return rMax;
}

rect FindRect(const char* file)
{
init_2(file);
rect rMax = {0,0,0,0};
if(num == 0){
rMax.width = width;
rMax.height = height;
return rMax;
}
rect rc;
for(int i = 0; i < num; i++){
_pos = &pos_set_x[i];
rc = FindMaxArea(rMax);
if(rMax.area() < rc.area()) rMax = rc;
}
return rMax;
}Top

42 楼aliceZOOZ（alice）回复于 2002-03-02 18:48:31 得分 0

重复一遍，数据绝对正确，大家可以编写一个简单的，O(n^3)的算法来验算。
happy5的矩形区域是宽2504。高5000，面积12520000：对角坐标(0, 2500), (2504, 7500)
Top

43 楼aliceZOOZ（alice）回复于 2002-03-02 18:52:20 得分 0

intfree的算法是O(n^2)且是对的，有兴趣可以去看一下。但现在我希望得到，向Zig说的那样，更低复杂度的算法，或者O(n^3)+剪枝可以出解的方法。Top

44 楼lonelyflyer（狮山小妖）回复于 2002-03-02 19:15:45 得分 1

lft_x = -1;

while( true )
{
lft_x = nxt_x( lft_x ); if( lft_x == MAXINT ) break;
lft_y = get_y( lft_x );
rgh_x = lft_x;
while( true )
{
rgh_x = nxt_x( rgh_x ); if( rgh_x == MAXINT ) break;
rgh_y = get_y( rgh_x );
area = (rgh_x - lft_x) * abs(lft_y - rgh_y);
max_area = max( area, max_area );
}
}
// nxt_x( int ): get next least x coordinate
// if input is -1, get the least x,
// if arrive at the rightest, return MAXINT
// get_y( int ): get corresponding y coordinateTop

45 楼aliceZOOZ（alice）回复于 2002-03-02 20:12:59 得分 0

to lonelyflyer(一个人飞)
浴场的左上和右下两个点一般来说不会是产奶点，不知道你的算法考虑到这一点了没有。Top

46 楼h8135（tiger0）回复于 2002-03-02 21:45:57 得分 0

to alice: 你是对的。在处理每个象限的第一个点和最后一个点时有一种特殊情况没有考虑到。修改后的代码如下，在处理每个象限的函数里增加了四个语句，所有的测试数据通过。
不过，此程序找到的区域和你的位置不同，是(2496,2500)到(7504，5000)

void ScanEN(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(EN_index == 0) {
bottom = findbottom_r(width);
SetMaxRect(rMax,pos.x,width,0,bottom);

left = findleft_t(0);
SetMaxRect(rMax,left,width,0,pos.y);
return;
}

right = pos_set_x[EN_list[0]].x;
bottom = findbottom_r(right);
SetMaxRect(rMax,pos.x,right,0,bottom);

left = findleft_t(0);
SetMaxRect(rMax,left,right,0,pos.y);

for(int i = 0; i < EN_index - 1; i++) {
top = pos_set_x[EN_list[i]].y;
right = pos_set_x[EN_list[i + 1]].x;
bottom = findbottom_r(right);
SetMaxRect(rMax,pos.x,right,top,bottom);

left = findleft_t(top);
SetMaxRect(rMax,left,right,top,pos.y);
}

top = pos_set_x[EN_list[EN_index - 1]].y;
left = findleft_t(top);
SetMaxRect(rMax,left,width,top,pos.y);

bottom = findbottom_r(width);
SetMaxRect(rMax,pos.x,width,top,bottom);
}

void ScanES(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(ES_index == 0) {
top = findtop_r(width);
SetMaxRect(rMax,pos.x,width,top,height);

left = findleft_b(height);
SetMaxRect(rMax,left,width,pos.y,height);
return;
}

right = pos_set_x[ES_list[0]].x;
top = findtop_r(right);
SetMaxRect(rMax,pos.x,right,top,height);

left = findleft_b(height);
SetMaxRect(rMax,left,right,pos.y,height);

for(int i = 0; i < ES_index - 1; i++) {
bottom = pos_set_x[ES_list[i]].y;
right = pos_set_x[ES_list[i + 1]].x;
top = findtop_r(right);
SetMaxRect(rMax,pos.x,right,top,bottom);

left = findleft_b(bottom);
SetMaxRect(rMax,left,right,pos.y,bottom);
}

bottom = pos_set_x[ES_list[ES_index - 1]].y;
left = findleft_b(bottom);
SetMaxRect(rMax,left,width,pos.y,bottom);

top = findtop_r(width);
SetMaxRect(rMax,pos.x,width,top,bottom);
}

void ScanWN(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(WN_index == 0) {
bottom = findbottom_l(0);
SetMaxRect(rMax,0,pos.x,0,bottom);

right = findright_t(0);
SetMaxRect(rMax,0,right,0,pos.y);
return;
}

left = pos_set_x[WN_list[0]].x;
bottom = findbottom_l(left);
SetMaxRect(rMax,left,pos.x,0,bottom);

right = findright_t(0);
SetMaxRect(rMax,left,right,0,pos.y);

for(int i = 0; i < WN_index - 1; i++) {
top = pos_set_x[WN_list[i]].y;
left = pos_set_x[WN_list[i + 1]].x;
bottom = findbottom_l(left);
SetMaxRect(rMax,left,pos.x,top,bottom);

right = findright_t(top);
SetMaxRect(rMax,left,right,top,pos.y);
}

top = pos_set_x[WN_list[WN_index - 1]].y;
right = findright_t(top);
SetMaxRect(rMax,0,right,top,pos.y);

bottom = findbottom_l(0);
SetMaxRect(rMax,0,pos.x,top,bottom);
}

void ScanWS(rect& rMax)
{
position& pos = *_pos;
int top,left,bottom,right;
if(WS_index == 0){
top = findtop_l(0);
SetMaxRect(rMax,0,pos.x,top,height);

right = findright_b(height);
SetMaxRect(rMax,0,right,pos.y,height);
return;
}

left = pos_set_x[WS_list[0]].x;
top = findtop_l(left);
SetMaxRect(rMax,left,pos.x,top,height);

right = findright_b(height);
SetMaxRect(rMax,left,right,pos.y,height);

for(int i = 0; i < ES_index - 1; i++) {
bottom = pos_set_x[ES_list[i]].y;
left = pos_set_x[ES_list[i + 1]].x;
top = findtop_l(left);
SetMaxRect(rMax,left,pos.x,top,bottom);

right = findright_b(bottom);
SetMaxRect(rMax,left,right,pos.y,bottom);
}

bottom = pos_set_x[WS_list[WS_index - 1]].y;
right = findright_b(bottom);
SetMaxRect(rMax,0,right,pos.y,bottom);

top = findtop_l(0);
SetMaxRect(rMax,0,pos.x,top,bottom);
}
Top

47 楼aliceZOOZ（alice）回复于 2002-03-03 14:33:06 得分 0

我再仔细看看Top

48 楼czy888（）回复于 2002-03-04 12:38:53 得分 5

高手发言了！
此题的时间复杂度为 O(N*logN)。Top

49 楼aliceZOOZ（alice）回复于 2002-03-04 14:57:19 得分 0

to czy888():我也听说有，但不知具体如何做。能否详述？Top

50 楼czy888（）回复于 2002-03-04 15:59:03 得分 0

此题的时间复杂度为 O(N*logN)。

其实 h8135(tiger0)已经想到了:)

原理上用分治法求解，具体实现使用递归方法。
==============================================
设 rect 表示奶牛们所在的矩形，n是奶牛的个数
f(rect,n)计算并返回最大的浴场。

则f(rect,n)的递归程序如下：
=========================
f(rect,n) 等于

1、如果n == 0，返回rect; （注：矩形中无牛，整个作浴场）

2、如果n > 0，考虑奶牛n,位置为 (Xn,Yn)
（1）用水平直线 Y=Yn 将矩形划分为上下两个部分rect_up, rect_down,
把n头奶牛按位置分到两个矩形中；
对rect_up中的n1头牛递归调用f(rect_up, n1) 求出浴场1
对rect_down中的n2头牛递归调用f(rect_down, n2) 求出浴场2
（2）同（1）
用垂直直线 X=Xn 将矩形划分为左右两个部分rect_right, rect_left
把n头奶牛按位置分到两个矩形中；
对rect_left中的n3头牛递归调用f(rect_left, n3) 求出浴场3