2019ccpc 秦皇岛站 A题 hdu6731

计算几何

注意点：

1. map存极角排序好的向量
2. 使用count减少时间和内存消耗
3. 分别处理直角点是查询点与直角点不是查询点这两种情况 离线搞

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=2005;
const db eps=1e-8;
int dcmp(ll x){
    if(x==0) return 0;
    else return x<0?-1:1;
}
struct V{
    db x,y;
    V(){}
    V(ll x,ll y):x(x),y(y){}
    V operator +(V v){return V(x+v.x,y+v.y);}
    V operator -(V v){return V(x-v.x,y-v.y);}
    bool operator <(V v)const{
        if(quad()!=v.quad()) return quad()>v.quad();
        else return dcmp(x*v.y-y*v.x)==1;
    }
    bool operator ==(V v)const{
        return dcmp(x-v.x)==0&&dcmp(y-v.y)==0;
    }
    int quad()const{return dcmp(y)==1||(dcmp(y)==0&&dcmp(x)>=0);}
};
ll dot(V v1,V v2){return v1.x*v2.x+v1.y*v2.y;}
ll det(V v1,V v2){return v1.x*v2.y-v1.y*v2.x;}
map<V,int>m;
V a[N],b[N];
int ans[N];
int main(){
    int n,q;
    while(cin>>n>>q){
        m.clear();
        memset(ans,0,sizeof(ans));
        for(int i=0;i<n;i++)
            cin>>a[i].x>>a[i].y;
        for(int i=0;i<q;i++)
            cin>>b[i].x>>b[i].y;
        V t;
        for(int i=0;i<q;i++){
            m.clear();
            for(int j=0;j<n;j++){
                t=b[i]-a[j];
                m[t]++;
            }
            for(int j=0;j<n;j++){
                t=b[i]-a[j];
                swap(t.x,t.y);
                t.x=-t.x;
                if(m.count(t)) ans[i]+=m[t];
                t.x=-t.x,t.y=-t.y;
                if(m.count(t)) ans[i]+=m[t];
            }
            ans[i]/=2;
        }
        for(int i=0;i<n;i++){
            m.clear();
            for(int j=0;j<n;j++){
                if(i!=j){
                    t=a[i]-a[j];
                    m[t]++;
                }
            }
            for(int j=0;j<q;j++){
                t=b[j]-a[i];
                swap(t.x,t.y);
                t.x=-t.x;
                if(m.count(t)) ans[j]+=m[t];
                t.x=-t.x,t.y=-t.y;
                if(m.count(t)) ans[j]+=m[t];
            }
        }
        for(int i=0;i<q;i++) cout<<ans[i]<<endl;
    }
    return 0;
}

最后

以上就是温婉小熊猫为你收集整理的2019ccpc 秦皇岛站 A题 hdu6731的全部内容，希望文章能够帮你解决2019ccpc 秦皇岛站 A题 hdu6731所遇到的程序开发问题。

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