hdu6731 Angle Beats（ccpc秦皇岛A，计算几何）

发布时间：2020-12-13 21:25:41 所属栏目：PHP教程来源：网络整理

导读：题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6731 题意：给出$n$个点，有$q$次询问每次询问给出一个点$b$，求这$n+1$个点，组成直角三角形并且包含$b$的组合有多少种数据范围： $1leq n leq 2000$ $1leq q leq 2000$ 分析：? 分类讨论当

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6731

题意：

给出$n$个点，有$q$次询问

每次询问给出一个点$b$，求这$n+1$个点，组成直角三角形并且包含$b$的组合有多少种

数据范围：

$1leq n leq 2000$

$1leq q leq 2000$

分析：?

分类讨论

当询问点作为直角。让$n$个点和$b$建立向量，其中向量化为最简，求互相垂直的向量对，可以枚举向量，求垂直向量
当给出的初始点作为直角，以每个初始点为偏移，建立向量，再枚举$b$点，求互相垂直的向量对

最简向量，首先除去gcd，如果x为负数，向量取反，如果x为0，y为负数，向量取反，这样唯一确定向量的方向了

注意：int就够了，longlong会超时

还有一个更快的方法：直接存x，y不化简，在向量比较时，直接比较斜率，如果即大于又小于那么这两个向量相等

AC代码：

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=2007;
pii a[maxn],b[maxn];
int n,q,ans[maxn];
int mygcd(int a,int b){
    if(b==0)return a;
    return mygcd(b,a%b);
}
pii getp(int x,int y){
    int tem=mygcd(x,y);
    x/=tem,y/=tem;
    if(x<0)x=-x,y=-y;
    else if(x==0&&y<0)y=-y;
    return make_pair(x,y);
}
map<pii,int>ma;
int main(){
    while(scanf("%d %d",&n,&q)==2){
        for(int i=1;i<=n;i++)scanf("%d %d",&a[i].first,&a[i].second);
        for(int i=1;i<=q;i++)scanf("%d %d",&b[i].first,&b[i].second);
        for(int i=1;i<=q;i++){
            ma.clear();
            for(int j=1;j<=n;j++){
                int x=a[j].first-b[i].first,y=a[j].second-b[i].second;
                ma[getp(x,y)]++;
                if(ma.count(getp(-y,x)))ans[i]+=ma[getp(-y,x)];
            }
        }
      // for(int i=1;i<=q;i++)printf("%dn",ans[i]),ans[i]=0;
        //cout<<"cdsafa"<<endl;
        for(int i=1;i<=n;i++){
            ma.clear();
            for(int j=1;j<=n;j++){
                if(j==i)continue;
                int x=a[j].first-a[i].first,y=a[j].second-a[i].second;
                ma[getp(x,y)]++;
            }
            for(int j=1;j<=q;j++){
                int x=b[j].first-a[i].first,y=b[j].second-a[i].second;
                if(ma.count(getp(-y,x)))ans[j]+=ma[getp(-y,x)];
            }
        }
        for(int i=1;i<=q;i++)printf("%dn",ans[i]=0;
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!