当前位置: 首页 > news >正文

题解:AT_arc082_c [ARC082E] ConvexScore

题意:很简单了,不再赘述。

做法:

首先我们注意到这个代价给的非常奇怪,他可以直接说是除了顶点但是还是要做减法,我们不妨先把这些点和内部的点视为一个点集。

然后我们发现我们并不会求一个随意点的平面上有多少个凸包,所以这个 \(2\) 为底数一定是非常有说法的,很常见的是我们转化为内部的那些点每个都可以选或不选,这样统计答案。

我们发现一个很神奇的事情,这样考虑就等于我们随一个点集,我们直接令他们的凸包围住他就可以了,只要要求随出来的点集不是全部共线即可。

那么答案就是 \(2^n\) 减去共线情况,我们直接枚举两端端点并算出来中间有多少个,假设是 \(x\) 个,那么就减去 \(2^x\) 的贡献。

注意减去单点和空集的答案。

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, mod = 998244353;
int x[maxn], y[maxn], n, pw[maxn];
double slope(int i, int j) {if(x[i] == x[j])return 1e9;return (y[j] - y[i]) / (double)(x[j] - x[i]);
}
signed main() {cin >> n;int ans = 1; pw[0] = 1;for (int i = 1; i <= n; i++)cin >> x[i] >> y[i], ans = ans * 2 % mod, pw[i] = ans;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {int cnt = 0;for (int k = i + 1; k < j; k++)cnt += (slope(i, k) == slope(k, j));ans = (ans - pw[cnt] + mod) % mod;}cout << (ans - n - 1 + mod) % mod << endl;return 0;
}
http://www.sczhlp.com/news/11057/

相关文章:

  • 金仓数据库kingbase创建计划任务
  • 无源探头选型指南:从参数解析到场景适配
  • 在K8S中,kube-apiserver和kube-scheduler的作用是什么?
  • Nature Genetics | 单核染色质鉴定抑郁症关键细胞类型与变异位点
  • 2025年打造知识驱动的软件工厂:主流平台评估与工程知识管理演进
  • 永久关闭windows10实时保护
  • PandaWiki 使用心得
  • 重组蛋白表达与纯化|蛋白表达不同标签的优势及用途
  • 基于PyTorch与注意力机制的验证码智能识别方法
  • CF1327F AND Segments
  • [原创]《C#高级GDI+实战:从零开发一个流程图》第09章:增加贝塞尔曲线,上、下、左、右连接点
  • 地球online
  • ICF RFIC25 Wu
  • OpenHarmony相关链接
  • 基于Python与CNN-CTC的端到端验证码识别方法研究
  • 说说内存泄漏的常见场景和排查方案?
  • FFmpeg 8.0 将集成 Whisper,支持实时字幕和转录;DeepMind 生物声学模型从鸟类拓展到哺乳昆虫和两栖丨日报
  • 手动修改 spring-boot 可执行jar包内的jar包,解决用压缩工具修改jar包后导致 java.lang.IllegalStateException
  • 20个非常有用的Python单行代码
  • MySQL十个常见问题及解决方法!
  • 微服务项目中基于 Servlet 的业务模块与 WebFlux 网关模块的 Redis 统一化配置教程
  • TINYINT(1)和BIT(1),到底该用哪个?
  • 8.13——962G(线段树查询区间min数量trick)
  • ARM intrinsics 指令集介绍 - Gather/Scatter
  • 召回场景- PforDelta Unpack 算子
  • 【PostgreSQL17】6 条件表达式
  • umask 权限掩码
  • 基于视觉推理的Img2LaTeX转换技术突破
  • docker常见命令汇总
  • mysql5.7 版本 only_full_group_by 导致原 sql 语句报错