2017 Russian Code Cup (RCC 17), Elimination Round D - Acute Triangles
2024-10-13 10:58:14
思路:
极角排序+点积叉积
在一个三角形中,如果它是直角或者顿角三角形,那么直角和顿角只会出现一次
所以直角和顿角三角形的个数等于直角和顿角的个数
所以锐角三角形的个数等于三元组个数减去直角和顿角的个数
三点共线看成退化的顿角三角形
怎么算直角和顿角个数呢, 先按某个点极角排序,然后暴力过取,用双指针维护到
当前幅角距离为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 ;
}
最新文章
- MyBatis1:MyBatis入门
- Oracle Linux
- Python—>;Mysql—>;Dbvisualizer
- jsp表格数据导出到Execl
- [RabbitMQ] AMQP close-reason, initiated by Library, code=541
- 移动Web应用开发入门指南——交互篇
- Codeforces 167B Wizards and Huge Prize(概率dp)
- c/c++中动态内存分配处理字符串的细节问题
- Mysqldump记录
- C# ;字符串加密解密函数
- 关于config文件中AppSettings和ConnectionStrings的用法跟区别(转)
- H5视频直播扫盲
- 如何用jQuery获取选中行固定列的数据
- 编辑你的数学公式——markdown中latex的使用
- AIX文件系统和存储部署(转)
- 浅谈jmeter请求参数获取的方式
- 软件架构设计学习总结(4):大数据架构hadoop
- TensoFlow的tf.reshape()
- jQuery 插件运行机制和 $冲突解决
- No.01——配置编程环境