题目大意:
在一个平面上,有\(N\)个点,求这些点构成的直角三角形个数。
解题思路:
枚举直角顶点,对于每个点,将这个点当做原点,对其他点按极角排序,然后双指针扫一遍,判断弧度差即可。

C++ Code:

#include<bits/stdc++.h>
#define eps 1e-15
typedef long long LoveLive;
struct point{
LoveLive x,y;double deg;
inline bool operator <(const point&rhs)const{return deg<rhs.deg;}
}a[1501],b[1501];
inline int readint(){
int c=getchar(),d=0,f=0;
for(;!isdigit(c);c=getchar())f=c=='-';
for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');
return f?-d:d;
}
int n;unsigned ans=0;
int main(){
n=readint();
for(int i=1;i<=n;++i)a[i].x=readint(),a[i].y=readint();
for(int i=1;i<=n;++i){
memcpy(b,a,sizeof a);
std::swap(b[i],b[1]);
for(int j=2;j<=n;++j)
b[j].deg=atan2(b[j].y-b[1].y,b[j].x-b[1].x);
std::sort(b+2,b+n+1);
int p1=2,p2=3,n1,n2;
for(;p1<=n;++p1){
n1=n2=1;
while((p2>=p1&&b[p2].deg-b[p1].deg<M_PI_2-eps)||(p2<p1&&b[p1].deg-b[p2].deg>M_PI_2*3+eps)){
++p2;
if(p2>n)p2=2;
if(p2==p1)break;
}
if(p1==p2)break;
if((p2>=p1&&b[p2].deg-b[p1].deg>M_PI_2+eps)||(p2<p1&&b[p1].deg-b[p2].deg<M_PI_2*3-eps))continue;
while(p1<n&&fabs(b[p1].deg-b[p1+1].deg)<eps)++p1,++n1;
while(p2<n&&fabs(b[p2].deg-b[p2+1].deg)<eps)++p2,++n2;
ans+=n1*n2;
}
}
printf("%u\n",ans);
return 0;
}

最新文章

  1. mybatis实战教程(mybatis in action)之一:开发环境搭建
  2. URAL 1932 The Secret of Identifier 题解
  3. centos安装配置nginx
  4. Nob畅想在线教育
  5. ED/EP系列5《消费指令》
  6. SQLite数据库的加密【转】
  7. JavaC 编译目录下所有的UTF-8编码的java文件
  8. Eclipse中设置在创建新类时自动生成注释的方法
  9. JQuery ajax调用asp.net的webMethod
  10. OCP-1Z0-042-V12.39-47题
  11. “ASP.default_aspx”并不包括“DropDownList1_SelectedIndexChanged”的定义,其解决方法。
  12. iOS内购(IAP)中的那些坑
  13. 广度优先搜索(BFS)——迷宫的最短路径
  14. thinkphp传参
  15. django搭建web (二) urls.py
  16. MongoDb安装和快速入门
  17. [Swift]LeetCode179. 最大数 | Largest Number
  18. Java 清理和垃圾回收
  19. (笔记)Linux内核学习(三)之进程调度
  20. 如何取消一个目录的git初始化

热门文章

  1. 封装基于jq弹窗插件
  2. GNU/Linux分支图
  3. SurgingFunction
  4. 经典alsa 录音和播放程序
  5. C# XML 反序列化解析
  6. BA-楼宇自控系统设计论文(转载)潘翌庆 元晨
  7. Vijos——T 1016 北京2008的挂钟 || 洛谷—— P1213 时钟
  8. [SharePoint2010开发入门经典]一、SPS2010介绍
  9. POJ 3177--Redundant Paths【无向图添加最少的边成为边双连通图 &amp;amp;&amp;amp; tarjan求ebc &amp;amp;&amp;amp; 缩点构造缩点树】
  10. PHP别名引用错误:“The use statement with non-compound name … has no effect”