【HDOJ6731】Angle Beats(极角排序)
2024-10-07 09:18:18
题意:二维平面上给定n个整点,q个询问
每个询问给定另外的一个整点,问其能与n个整点中任意取2个组成的直角三角形的个数
保证所有点位置不同
n<=2e3,q<=2e3,abs(x[i],y[i])<=1e9
思路:
对于每个询问点q,分两类讨论
一:q为直角顶点
以q为原点,求出它到n个点的向量,极角排序
枚举一个向量,其贡献为平行于该向量逆时针转90度的向量的个数
二:q不为直角顶点
枚举直角顶点i作为原点,求出它到另外n-1个点的向量,极角排序
对于q,其贡献为:设t为i到q的向量,平行于t逆时针或顺时针转90度的向量的个数
用upper_bound-lower_bound计算个数
极度卡时,在HDOJ上TLE,在gym上4s时限3sA的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 4100
#define M 2000010
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int dx[]={-,,,};
int dy[]={,,-,}; struct P
{
int x,y;
P()=default;
P(int x,int y):x(x),y(y){}
P rot90(){return P(-y,x);} //逆时针转90度
P _rot90(){return P(y,-x);} //顺时针转90度
}p[N],t[N]; bool operator^(P a,P b) //叉积
{
return (1ll*a.x*b.y-1ll*a.y*b.x)>;
} int quadrant(P a) //象限
{
if(a.x>&&a.y>=) return ;
else if(a.x<=&&a.y>) return ;
else if(a.x<&&a.y<=) return ;
else if(a.x>=&&a.y<) return ;
} bool operator<(P a,P b) //极角排序
{
int qa=quadrant(a),qb=quadrant(b);
if(qa!=qb) return qa<qb;
return a^b;
} P operator-(P a,P b)
{
return P(a.x-b.x,a.y-b.y);
} int ans[N],n,q; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void solve()
{
rep(i,,q) ans[i]=;
int m=n+q;
rep(i,n+,m)
{
int top=;
rep(j,,n)
{
top++;
t[top]=p[j]-p[i];
}
sort(t+,t+top+);
rep(j,,n)
{
P tmp=t[j].rot90();
int num=upper_bound(t+,t+top+,tmp)-lower_bound(t+,t+top+,tmp);
ans[i-n]+=num;
}
}
rep(i,,n)
{
int top=;
rep(j,,n)
if(j!=i)
{
top++;
t[top]=p[j]-p[i];
}
sort(t+,t+top+);
rep(j,n+,m)
{
P tmp=p[j]-p[i];
P t1=tmp.rot90();
ans[j-n]+=upper_bound(t+,t+top+,t1)-lower_bound(t+,t+top+,t1);
P t2=tmp._rot90();
ans[j-n]+=upper_bound(t+,t+top+,t2)-lower_bound(t+,t+top+,t2);
}
}
rep(i,,q) printf("%d\n",ans[i]);
} int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
rep(i,,n+q) p[i].x=read(),p[i].y=read();
solve();
}
return ;
}
最新文章
- Android立体旋转动画实现与封装(支持以X、Y、Z三个轴为轴心旋转)
- 关于LESS
- 数据存储_SQLite (2)
- ssh问题
- Codeforces 720A. Closing ceremony
- [转]SQLite C/C++
- centos下cp -r 命令可拷贝文件夹
- 【技术贴】jsp出现getOutputStream() has already been calle
- HDU 5727 - Necklace
- Dollar Dayz(大数母函数,高低位存取)
- Web API核查表:设计、测试、发布API时需思考的43件事[转]
- linux性能调试之vmstat
- C#中类成员的执行顺序
- CentOS 6.8 配置防火墙,开放8080端口
- UART、SPI和I2C详解
- ubuntu安装matplotlib一些坑
- Python语言说明
- 设计模式教程(Design Patterns Tutorial)笔记之一 创建型模式(Creational Patterns)
- Spark笔记-DataSet,DataFrame
- 搭建ReactNative时的最普遍的错误—— ";:CFBundleIdentifier";, Does Not Exist