D - Acute Triangles

思路:

极角排序+点积叉积

在一个三角形中,如果它是直角或者顿角三角形,那么直角和顿角只会出现一次

所以直角和顿角三角形的个数等于直角和顿角的个数

所以锐角三角形的个数等于三元组个数减去直角和顿角的个数

三点共线看成退化的顿角三角形

怎么算直角和顿角个数呢, 先按某个点极角排序,然后暴力过取,用双指针维护到

当前幅角距离为pi/2 到 3*pi/2 的区间, 区间内点的个数就是到当前幅角为直角或顿角的个数

可以用点积和叉积分别判断角度和相对方向

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-(long double)1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e3 + ;
struct point {
LL x, y;
point(){}
point(LL x, LL y):x(x), y(y){}
LL dot(point p) {
return x*p.x + y*p.y;
}
LL cross(point p) {
return x*p.y - y*p.x;
}
}p[N], t[N];
bool anglecmp(point a, point b) {
if(a.y <= && b.y > ) return true;
if(a.y > && b.y <= ) return false;
if(!a.y && !b.y) return a.x < b.x;
return a.cross(b) > ;
}
bool acute(point a, point b) {
return a.dot(b) > && a.cross(b) >= ;
}
bool acute2(point a, point b) {
return a.dot(b) > && a.cross(b) < ;
}
int main() {
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%lld %lld", &p[i].x, &p[i].y);
LL ans = 1LL*n*(n-)*(n-)/;
for (int i = ; i <= n; i++) {
int cnt = ;
for (int j = ; j <= n; j++) {
if(j!=i)
t[++cnt] = point(p[j].x - p[i].x, p[j].y - p[i].y);
}
sort(t+, t++cnt, anglecmp);
int l = , r = ;
for (int j = ; j <= cnt; j++) {
while(l <= cnt && acute(t[j], t[l])) l++;
while(r <= cnt && !acute2(t[j], t[r])) r++;
ans -= r-l;
}
}
printf("%lld\n", ans);
}
return ;
}

最新文章

  1. MyBatis1:MyBatis入门
  2. Oracle Linux
  3. Python—&gt;Mysql—&gt;Dbvisualizer
  4. jsp表格数据导出到Execl
  5. [RabbitMQ] AMQP close-reason, initiated by Library, code=541
  6. 移动Web应用开发入门指南——交互篇
  7. Codeforces 167B Wizards and Huge Prize(概率dp)
  8. c/c++中动态内存分配处理字符串的细节问题
  9. Mysqldump记录
  10. C#&nbsp;字符串加密解密函数
  11. 关于config文件中AppSettings和ConnectionStrings的用法跟区别(转)
  12. H5视频直播扫盲
  13. 如何用jQuery获取选中行固定列的数据
  14. 编辑你的数学公式——markdown中latex的使用
  15. AIX文件系统和存储部署(转)
  16. 浅谈jmeter请求参数获取的方式
  17. 软件架构设计学习总结(4):大数据架构hadoop
  18. TensoFlow的tf.reshape()
  19. jQuery 插件运行机制和 $冲突解决
  20. No.01——配置编程环境

热门文章

  1. F#周报2019年第3期
  2. 前后端分离项目,标准json协议格式参考
  3. python摸爬滚打之day15----初识类
  4. Manjaro 玩机记录
  5. UIScrollView上面的UIButton点击始终在中间
  6. web状态管理机制
  7. postgres密码修改
  8. node(03)--利用 HTTP 模块 URl 模块 PATH 模块 FS 模块创建一个 WEB 服务器
  9. taro中子父传值
  10. Go 初体验 - channel.1 - 基本用法