【双指针】Square Pasture G（P7153）

本文主要是介绍【双指针】Square Pasture G（P7153），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

P7153

---

题目大意

给你平面上的若干点，让你画一个正方形，问框住的点有多少种组合

---

解题思路

先枚举正方形左右两边的点，然后用双指针计算正方形移动过程中1框住的点

然后把所有点x,y坐标取反，再做一次，这样可以把以上下/左右点为边界的正方形都计算出来

最后减去上下左右都有点的正方形去重

---

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++;//不会框到上下面的点while(d[r]<=d[l]+len&&r<=now){//在正方形范围内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;
}

这篇关于【双指针】Square Pasture G（P7153）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---