BZOJ 1914 计算几何
2024-08-31 02:50:27
思路:
我们可以算不合法的
如果三个点都在同一侧 就不合法..
用总方案数减掉就可以了
(有神奇的实现方法...)
//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=;
int n;long long ans;
struct Node{int x,y;double angle;}node[N];
bool operator<(Node a,Node b){return a.angle<b.angle;}
long long operator*(Node a,Node b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d",&node[i].x,&node[i].y);
node[i].angle=atan2(node[i].y,node[i].x);
}
sort(node+,node++n);
int cnt=,r=;
for(int i=;i<=n;i++){
while(r%n+!=i&&node[i]*node[r%n+]>)r++,cnt++;
ans-=1ll*cnt*(cnt-)/,cnt--;
}printf("%lld\n",1ll*n*(n-)*(n-)/+ans);
}
最新文章
- 复杂的 Hash 函数组合有意义吗?
- Eclipse启动Tomcat时server.xml和content.xml自动还原问题
- 高性能的JavaScript--数据访问(1)
- windows系统下npm 全局安装路径问题
- Android Volley框架的使用(5)
- 【LeetCode OJ】Binary Tree Level Order Traversal II
- Auto Clear Unity Console Log
- PHP:strpos()-返回字符串在另一个字符串中第一次出现的位置
- mvc权限,登陆,异常
- Qt多国语言
- erlang怎样有效监听大量并发连接
- [资料] Apache2 的 httpd.conf 经典中文翻译
- 重写系统中的UINavigationController返回按钮的事件
- const限定符的作用
- linux命令积累(Ubuntu)
- sqlserver 设置外键
- 利用mock提高效率
- 英语词汇(2)fall down,fall off和fall over
- Java开发知识之Java控制语句
- ruby select 方法,可用于先查询结果后,再次用条件限制
热门文章
- centos添加永久的环境变量
- Java程序员怎么不断进阶 必须要掌握哪些技能
- Django - 一对多跨表操作
- css3部分注意事项
- 28.function_score自定义相关度分数算法
- Python time &; random模块
- Linux - centos7 下 MySQL(mariadb) 和 主从复制
- .Net防sql注入的方法总结
- Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)
- hdu2012 素数判定【C++】