7.29 t1

7.29 t1

题目：

辣鸡ljh NOI之后就退役了，然后就滚去学文化课了。

然而在上化学课的时候，数学和化学都不好的ljh却被一道简单题难住了，受到了大佬的嘲笑。

题目描述是这样的：

在一个二维平面上有一层水分子，请问形成了多少个氢键？

这个二维平面可以看做一个类似棋盘的东西，每个格子可以容纳一个水分子，左下角的格子为(0,0)，这个格子右边的格子为(1,0)，上方格子为(0,1)，以此类推。

辣鸡ljh当然不会做了，所以他来求助JeremyGou，JeremyGou一眼就看穿了真相，并想用这道题来考一考正在做NOIP模拟赛的你。

注：在本题中，我们认为一个水分子能与和它曼哈顿距离为2且直线距离小于2的其他格子形成氢键。

输入格式

一个整数n

接下来n行，每行给出四个整数x1,y1,x2,y2

表示以(x1,y1)为左下角,(x2,y2)为右上角的矩形中每个格子都有一个水分子。

给出的所有矩形没有交集。

输出格式

一个整数，表示氢键的数量。

样例

样例输入1

3
0 0 0 0
0 1 1 2
2 2 2 3

样例输出1

5

样例输入2

10
1 8 8 9
0 3 10 7
0 0 7 0
0 2 9 2
4 10 8 10
10 0 10 2
0 10 0 10
8 0 9 1
0 8 0 9
9 8 10 8

样例输出2

157

数据范围与提示

分析：这题就是个大模拟。把矩形按x左排好，用扫描线一个一个来就行。但我真的没想到n方过十万，还不用卡常。这种题很练码力和耐心。

注意：ans+=2*(ju[i].xb-ju[i].xa)+1;这句话中的ans虽然是long long,但还是会爆，原因：int乘的时候中间爆掉了，即使ans开long long也没用。

解决办法：1.所有都开long long

　　　　　　2.加上 *1ll

code:

#include<bits/stdc++.h>
using namespace std;
struct aaa
{long long xa,ya,xb,yb;
}ju[100005];
long long ans,n;
inline long long read()
{long long x=0;bool f=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return f?-x:x;
}
bool cmp(aaa a,aaa b)
{if(a.xa!=b.xa)return a.xa<b.xa;if(a.xb!=b.xb)return a.xb<b.xb;return a.ya<b.yb;
}
void solve()
{for(int i=1;i<=n;i++)ans+=2*(ju[i].xb-ju[i].xa)*(ju[i].yb-ju[i].ya);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(ju[j].xa-ju[i].xb>1)break;if(ju[j].ya-ju[i].yb>1||ju[i].ya-ju[j].yb>1)continue;if(ju[i].xa==ju[j].xa){if(ju[i].xb<ju[j].xb)ans+=2*(ju[i].xb-ju[i].xa)+1;else if(ju[i].xb==ju[j].xb)ans+=2*(ju[i].xb-ju[i].xa);}else if(ju[j].xa<ju[i].xb){if(ju[j].xb<ju[i].xb)ans+=2*(ju[j].xb-ju[j].xa+1);else if(ju[j].xb==ju[i].xb)ans+=2*(ju[j].xb-ju[j].xa)+1;else ans+=2*(ju[i].xb-ju[j].xa+1);}else if(ju[j].xa==ju[i].xb){if(ju[i].xb-ju[i].xa>0)ans++;if(ju[j].xb-ju[j].xa>0)ans++;}else{if(ju[j].ya-ju[i].yb==1)ans+=1;else if(ju[j].ya==ju[i].yb){if(ju[j].yb-ju[j].ya>0)ans++;if(ju[i].yb-ju[i].ya>0)ans++;}else if(ju[i].ya==ju[j].yb){if(ju[j].yb-ju[j].ya>0)ans++;if(ju[i].yb-ju[i].ya>0)ans++;}else if(ju[i].ya-ju[j].yb==1)ans+=1;else{int isize=ju[i].yb-ju[i].ya+1,jsize=ju[j].yb-ju[j].ya+1;if(isize<jsize){if(ju[j].yb>ju[i].yb){if(ju[j].ya>ju[i].ya)ans+=2*(ju[i].yb-ju[j].ya+1);else if(ju[j].ya==ju[i].ya)ans+=2*isize-1;else ans+=2*isize;}else if(ju[j].yb==ju[i].yb)ans+=2*isize-1;else ans+=2*(ju[j].yb-ju[i].ya+1);}else if(isize==jsize){if(ju[j].yb>ju[i].yb)ans+=2*(ju[i].yb-ju[j].ya+1);else if(ju[j].yb==ju[i].yb)ans+=2*isize-2;else ans+=2*(ju[j].yb-ju[i].ya+1);}else{if(ju[j].yb>ju[i].yb)ans+=2*(ju[i].yb-ju[j].ya+1);else if(ju[i].yb==ju[j].yb)ans+=2*jsize-1;else {if(ju[j].ya>ju[i].ya)ans+=2*jsize;else if(ju[j].ya==ju[i].ya)ans+=2*jsize-1;else ans+=2*(ju[j].yb-ju[i].ya+1);}}}}}}cout<<ans;
}
int main()
{n=read();for(int i=1;i<=n;i++){ju[i].xa=read();ju[i].ya=read();ju[i].xb=read();ju[i].yb=read();}sort(ju+1,ju+n+1,cmp);solve();return 0;
}

转载于:.html