| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这代码实在不知道哪里错了,求大神帮我解决一下吧~~~~#include <stdio.h>
#include <memory.h>
int max, Acount, Bcount, a[200][3], b[200][3], rec[40010][4];
int t, xtotal, ytotal, cur, flag[40010], ptr;
int CanCut(int xl, int yl, int xh, int yh)
{
int i;
for(i=0; i<Acount; i++)
{
if( (xl >= a[i][0]) && (xh <= a[i][1]) && (a[i][2] <yh ) && (a[i][2] > yl) )
{
rec[cur][0] = xl; rec[cur][1] = yl; rec[cur][2] = xh; rec[cur][3] = a[i][2]; flag[cur] = 1;
cur++;
rec[cur][0] = xl; rec[cur][1] = a[i][2]; rec[cur][2] = xh; rec[cur][3] = yh; flag[cur] = 1;
cur++;
return 1;
}
}
for(i=0; i<Bcount; i++)
{
if( (yl >= b[i][0]) && (yh <= b[i][1]) && (b[i][2] < xh) && (b[i][2] > xl) )
{
rec[cur][0] = xl; rec[cur][1] = yl; rec[cur][2] = b[i][2]; rec[cur][3] = yh; flag[cur] = 1;
cur++;
rec[cur][0] = b[i][2]; rec[cur][1] = yl; rec[cur][2] = xh; rec[cur][3] = yh; flag[cur] = 1;
cur++;
return 1;
}
}
return 0;
}
int works()
{
int tmp, i;
memset(rec, 0, sizeof(rec));
memset(flag, 0, sizeof(flag));
ptr=0,cur=1;
flag[ptr]=1;
rec[ptr][0]=rec[ptr][1]=0;
rec[ptr][2]=xtotal;
rec[ptr][3]=ytotal;
while(ptr<cur)
{
if(flag[ptr] && CanCut(rec[ptr][0], rec[ptr][1], rec[ptr][2], rec[ptr][3]) )
flag[ptr]=0;
ptr++;
}
max = 0;
for(i=0; i<cur; i++)
{
if(flag[i])
{
tmp=(rec[i][2]-rec[i][0])*(rec[i][3]-rec[i][1]);
if(max<tmp)
max=tmp;
}
}
return max;
}
int Add(int res[][3], int len, int x, int y, int z)
{
int i;
int flag = 0;
for(i=0; i<len; i++)
{
if(res[i][2] == z && res[i][1] < y && res[i][0] < x && x<=res[i][1])
{
res[i][1] = y;
flag = 1;
}
if(res[i][2] == z && res[i][0] <= y && res[i][0] > x && y < res[i][1])
{
res[i][0] = x;
flag = 1;
}
if(res[i][2] == z && res[i][0] <= x && res[i][1] >= y)
{
flag = 1;
break;
}
if(res[i][2] == z && res[i][0] >= x && res[i][1] <= y)
{
res[i][0] = x;
res[i][1] = y;
flag = 1;
}
}
if(!flag)
{
res[len][0] = x;
res[len][1] = y;
res[len][2] = z;
len++;
}
return len;
}
int main()
{
//freopen("D:\\in.txt", "r", stdin);
//freopen("D:\\out.txt", "w", stdout);
int i;
int cases;
int xl, yl, xh, yh;
scanf("%d", &cases);
while(cases--)
{
Acount = 0;
Bcount = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%d%d", &xtotal, &ytotal);
scanf("%d",&t);
for(i=0; i<t; i++)
{
scanf("%d%d%d%d", &xl, &yl, &xh, &yh);
Acount = Add(a, Acount, xl, xh, yl); //xl, xh是切割线的两端,yl表示是一个矩形的下面一段的切割线。
Bcount = Add(b, Bcount, yl, yh, xh); //同理这个表示矩形右边的切割线。
}
printf("%d\n", works());
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator