社区讨论
5号6号WA求调
P1856[IOI 1998 / USACO5.5] 矩形周长 Picture参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m62y2llh
- 此快照首次捕获于
- 2025/01/19 09:34 去年
- 此快照最后确认于
- 2025/11/04 11:20 4 个月前
我的思路是用一个数组表示当前矩形某一条边,看看没有被其它矩形覆盖的有多少,所有矩形的四条边分别算一下就是结果了,结果5号6号WA了,还没想到哪里出了问题
CPP#include<bits/stdc++.h>
using namespace std;
struct st
{
int xl,xr,yd,yu;
};
int main()
{
long long n,i,j,ans=0,b[20002];
cin>>n;
st a[n];
for(i=0;i<n;i++)
cin>>a[i].xl>>a[i].yd>>a[i].xr>>a[i].yu;
for(i=0;i<n;i++)
{
for(j=0;j<=20001;j++)
b[j]=0;
for(j=0;j<n;j++)
{
if(j!=i && a[j].yd<a[i].yd && a[j].yu>a[i].yd)
{
b[a[j].xl+10000]++;
b[a[j].xr+10000]--;
}
if(j>i && (a[j].yd==a[i].yd || a[j].yu==a[i].yd))
{
b[a[j].xl+10000]++;
b[a[j].xr+10000]--;
}
}
for(j=1;j<=20001;j++)
b[j]+=b[j-1];
for(j=a[i].xl+10000;j<a[i].xr+10000;j++)
if(b[j]==0)
ans++;
for(j=0;j<=20001;j++)
b[j]=0;
for(j=0;j<n;j++)
{
if(j!=i && a[j].yd<a[i].yu && a[j].yu>a[i].yu)
{
b[a[j].xl+10000]++;
b[a[j].xr+10000]--;
}
if(j>i && (a[j].yd==a[i].yu || a[j].yu==a[i].yu))
{
b[a[j].xl+10000]++;
b[a[j].xr+10000]--;
}
}
for(j=1;j<=20001;j++)
b[j]+=b[j-1];
for(j=a[i].xl+10000;j<a[i].xr+10000;j++)
if(b[j]==0)
ans++;
for(j=0;j<=20001;j++)
b[j]=0;
for(j=0;j<n;j++)
{
if(j!=i && a[j].xl<a[i].xl && a[j].xr>a[i].xl)
{
b[a[j].yd+10000]++;
b[a[j].yu+10000]--;
}
if(j>i && (a[j].xl==a[i].xl || a[j].xr==a[i].xl))
{
b[a[j].yd+10000]++;
b[a[j].yu+10000]--;
}
}
for(j=1;j<=20001;j++)
b[j]+=b[j-1];
for(j=a[i].yd+10000;j<a[i].yu+10000;j++)
if(b[j]==0)
ans++;
for(j=0;j<=20001;j++)
b[j]=0;
for(j=0;j<n;j++)
{
if(j!=i && a[j].xl<a[i].xr && a[j].xr>a[i].xr)
{
b[a[j].yd+10000]++;
b[a[j].yu+10000]--;
}
if(j>i && (a[j].xl==a[i].xr || a[j].xr==a[i].xr))
{
b[a[j].yd+10000]++;
b[a[j].yu+10000]--;
}
}
for(j=1;j<=20001;j++)
b[j]+=b[j-1];
for(j=a[i].yd+10000;j<a[i].yu+10000;j++)
if(b[j]==0)
ans++;
}
cout<<ans;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...