网站开发工资一般多少钱,小程序商城怎么开通,巴州建设工程信息网,百度快照的作用是什么正题
P7153 题目大意
给你平面上的若干点#xff0c;让你画一个正方形#xff0c;问框住的点有多少种组合 解题思路
先枚举正方形左右两边的点#xff0c;然后用双指针计算正方形移动过程中1框住的点
然后把所有点x,y坐标取反#xff0c;再做一次#xff0c;这样可以把…正题
P7153 题目大意
给你平面上的若干点让你画一个正方形问框住的点有多少种组合 解题思路
先枚举正方形左右两边的点然后用双指针计算正方形移动过程中1框住的点
然后把所有点x,y坐标取反再做一次这样可以把以上下/左右点为边界的正方形都计算出来
最后减去上下左右都有点的正方形去重 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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.xb.x;
}
void solve()
{sort(a1,a1n,cmp);for(ll i1;in;i){d[now1]a[i].y;for(ll ji1;jn;j){d[now]a[j].y;for(ll know;k1;--k)if(d[k-1]d[k])swap(d[k],d[k-1]);else break;lena[j].x-a[i].x;if(abs(a[i].y-a[j].y)len)continue;minnmax(a[i].y,a[j].y)-len;maxxmin(a[i].y,a[j].y);l1;r1;d[0]-2000000001;d[now1]2000000001;while(d[l]minnlnow)l;while(d[r]minnlenrnow)r;while(d[l]maxxlnow){while((d[r1]-1)-(d[l-1]1)lenrnow)r;//不会框到上下面的点while(d[r]d[l]lenrnow){//在正方形范围内if(d[r]d[l]len)num;ans;r;}l;r--;}}}return;
}
int main()
{scanf(%lld,n);ansn1;for(ll i1;in;i)scanf(%lld%lld,a[i].x,a[i].y);solve();for(ll i1;in;i)swap(a[i].x,a[i].y);solve();printf(%lld,ans-num/2);return 0;
}
