题意:二维平面上给定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 ;
}

最新文章

  1. Android立体旋转动画实现与封装(支持以X、Y、Z三个轴为轴心旋转)
  2. 关于LESS
  3. 数据存储_SQLite (2)
  4. ssh问题
  5. Codeforces 720A. Closing ceremony
  6. [转]SQLite C/C++
  7. centos下cp -r 命令可拷贝文件夹
  8. 【技术贴】jsp出现getOutputStream() has already been calle
  9. HDU 5727 - Necklace
  10. Dollar Dayz(大数母函数,高低位存取)
  11. Web API核查表:设计、测试、发布API时需思考的43件事[转]
  12. linux性能调试之vmstat
  13. C#中类成员的执行顺序
  14. CentOS 6.8 配置防火墙,开放8080端口
  15. UART、SPI和I2C详解
  16. ubuntu安装matplotlib一些坑
  17. Python语言说明
  18. 设计模式教程(Design Patterns Tutorial)笔记之一 创建型模式(Creational Patterns)
  19. Spark笔记-DataSet,DataFrame
  20. 搭建ReactNative时的最普遍的错误—— &quot;:CFBundleIdentifier&quot;, Does Not Exist

热门文章

  1. [Mac Terminal] ___切换到其他路径和目录
  2. kafka学习(八)
  3. java中的命名规则
  4. docker--docker 的web可视化管理工具
  5. exists、in和join比较
  6. 正反向代理、负载均衡、Nginx配置实现
  7. java基础笔记)(5)
  8. P1079Vigen&#232;re密码
  9. [BZOJ 4332] [JSOI2012]分零食(DP+FFT)
  10. MAC设置环境变量