[COCI2007]PRAVOKUTNI
2024-08-31 12:17:59
题目大意:
在一个平面上,有\(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;
}
最新文章
- mybatis实战教程(mybatis in action)之一:开发环境搭建
- URAL 1932 The Secret of Identifier 题解
- centos安装配置nginx
- Nob畅想在线教育
- ED/EP系列5《消费指令》
- SQLite数据库的加密【转】
- JavaC 编译目录下所有的UTF-8编码的java文件
- Eclipse中设置在创建新类时自动生成注释的方法
- JQuery ajax调用asp.net的webMethod
- OCP-1Z0-042-V12.39-47题
- “ASP.default_aspx”并不包括“DropDownList1_SelectedIndexChanged”的定义,其解决方法。
- iOS内购(IAP)中的那些坑
- 广度优先搜索(BFS)——迷宫的最短路径
- thinkphp传参
- django搭建web (二) urls.py
- MongoDb安装和快速入门
- [Swift]LeetCode179. 最大数 | Largest Number
- Java 清理和垃圾回收
- (笔记)Linux内核学习(三)之进程调度
- 如何取消一个目录的git初始化
热门文章
- 封装基于jq弹窗插件
- GNU/Linux分支图
- SurgingFunction
- 经典alsa 录音和播放程序
- C# XML 反序列化解析
- BA-楼宇自控系统设计论文(转载)潘翌庆 元晨
- Vijos——T 1016 北京2008的挂钟 || 洛谷—— P1213 时钟
- [SharePoint2010开发入门经典]一、SPS2010介绍
- POJ 3177--Redundant Paths【无向图添加最少的边成为边双连通图 &;amp;&;amp; tarjan求ebc &;amp;&;amp; 缩点构造缩点树】
- PHP别名引用错误:“The use statement with non-compound name … has no effect”