正題

P7153

---

題目大意

給你平面上的若干點(diǎn)，讓你畫(huà)一個(gè)正方形，問(wèn)框住的點(diǎn)有多少種組合

---

解題思路

先枚舉正方形左右兩邊的點(diǎn)，然后用雙指針計(jì)算正方形移動(dòng)過(guò)程中1框住的點(diǎn)

然后把所有點(diǎn)x,y坐標(biāo)取反，再做一次，這樣可以把以上下/左右點(diǎn)為邊界的正方形都計(jì)算出來(lái)

最后減去上下左右都有點(diǎn)的正方形去重

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 221 using namespace std; ll n,l,r,len,ans,num,now,maxx,minn,d[N]; struct node {ll x,y; }a[N]; bool cmp(node a,node b) {return a.x<b.x; } void solve() {sort(a+1,a+1+n,cmp);for(ll i=1;i<=n;++i){d[now=1]=a[i].y;for(ll j=i+1;j<=n;++j){d[++now]=a[j].y;for(ll k=now;k>1;--k)if(d[k-1]>d[k])swap(d[k],d[k-1]);else break;len=a[j].x-a[i].x;if(abs(a[i].y-a[j].y)>len)continue;minn=max(a[i].y,a[j].y)-len;maxx=min(a[i].y,a[j].y);l=1;r=1;d[0]=-2000000001;d[now+1]=2000000001;while(d[l]<minn&&l<=now)l++;while(d[r]<minn+len&&r<=now)r++;while(d[l]<=maxx&&l<=now){while((d[r+1]-1)-(d[l-1]+1)<len&&r<=now)r++;//不會(huì)框到上下面的點(diǎn)while(d[r]<=d[l]+len&&r<=now){//在正方形范圍內(nèi)if(d[r]==d[l]+len)num++;ans++;r++;}l++;r--;}}}return; } int main() {scanf("%lld",&n);ans=n+1;for(ll i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);solve();for(ll i=1;i<=n;++i)swap(a[i].x,a[i].y);solve();printf("%lld",ans-num/2);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【双指针】Square Pasture G（P7153）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。