2019秦皇岛CCPC 计算几何

Angle Beats

题意：
给定2D平面上的n个点P1，P2，⋯，Pn和q个查询。 在第i个查询中，给出一个点Ai，您应确定1≤u<v≤n且Ai，Pu，Pv形成一个非退化直角三角形的元组（u，v）的数量。非退化三角形就是三个点不能在一条直线上。
题目地址：https://codeforces.com/gym/102361/problem/A
参考blog：https://www.cnblogs.com/gzr2018/p/11605356.html

思路

首先题目的时间限制了中总复杂度应该是n* n * log（n）或者说q * n * log（n），
此处q和n的范围一致。
通过叉乘定义点结构体的小于号，做到log级别的维护，此处非常巧妙，且通过base（）函数使得方向相反的向量当作相同的。
并且在每个询问点不是直角顶点的情况下 离线每个询问点，妙。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+4;
struct node{
long long x=0,y=0;
node(){}
node(int _x,int _y):x(_x),y(_y){}
node base()const
{
if(x<0||(x==0&&y<0))
{
return node(-x,-y);
}
return (*this);
}
bool operator<(const node & tmp)const
{//如果共线，考虑是相同的向量
node a=this->base();
node b=tmp.base();
return a.x*b.y<b.x*a.y;
}
node operator-(const node & tmp)const
{
return node(x-tmp.x,y-tmp.y);
}
}point[maxn],query[maxn];
int cnt_po=0;
int n,q;int tmpx,tmpy;long long ans[maxn];
map<node,int> mp;
int main()
{
while(cin>>n>>q)
{
memset(ans,0,sizeof(ans));
for(int j=0;j<n;j++)
{
cin>>tmpx>>tmpy;
point[j]=node(tmpx,tmpy);
}
for(int i=0;i<q;i++)
{
cin>>query[i].x>>query[i].y;
}
for(int i=0;i<q;i++)//求解作为直角顶点
{
mp.clear();
for(int j=0;j<n;j++)
{
mp[query[i]-point[j]]++;
}
for(int j=0;j<n;j++)
{
node p=query[i]-point[j];
p=node(-p.y,p.x);
ans[i]+=mp.count(p)?mp[p]:0;
}
ans[i]/=2;//由于两条直角边都会枚举，所以除2
}
for(int i=0;i<n;i++)/作为非直角顶点，每次枚举点i，作为直角顶点，更新全部的q组询问点
{
mp.clear();
for(int j=0;j<n;j++)
{
if(j==i)continue;
mp[point[j]-point[i]]++;
}
for(int j=0;j<q;j++)
{
node p=query[j]-point[i];
p=node(-p.y,p.x);
ans[j]+=mp.count(p)?mp[p]:0;
}
}
for(int j=0;j<q;j++)
printf("%I64dn",ans[j]);
}
return 0;
}

最后

以上就是美满蜜粉为你收集整理的2019秦皇岛CCPC 计算几何的全部内容，希望文章能够帮你解决2019秦皇岛CCPC 计算几何所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。