计算几何

bzoj 2146: Construct

Description 随着改革开放的深入推进…… 小T家要拆迁了…… 当对未来生活充满美好憧憬的小T看到拆迁协议书的时候，小T从一位大好的社会主义青年变成了绝望的钉子户。由于小T的家位于市中心，拆迁工作又难以进行，有关部门决定先把小T家用围栏…

【NOI2015模拟1.17】⑨

Description Cirno闲着无事的时候喜欢冰冻青蛙。 Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整…

【计算几何】判断多边形边界顺逆时针 C++代码实现

文章目录一、多边形边界顺序二、数学原理2.1 Green公式2.2 鞋带公式三、代码实现一、多边形边界顺序多边形可以由一个点集 { v 1 , v 2 , . . . , v n } \{v_1,v_2,...,v_n\} {v1,v2,...,vn} 表示，构成多边形的点集确定，多边形边界的顺序也就…

bzoj 2338: [HNOI2011]数矩形

Description 计算几何。枚举边，长度和中点都相同即可构成矩形，差积计算面积即可 #include<cstdio> #include<algorithm> using namespace std; int p; struct point {long long x,y; }a[1501]; struct line {long long x1,y1,x2,y2;long lon…

$HDU - 3126 Nova（二分+最大流+计算几何）$

HDU - 3126 Nova（二分+最大流+计算几何）

链接：https://cn.vjudge.net/problem/HDU-3126 题意：多组样例，n个巫师，m个敌人，k颗树。巫师有攻击距离和冷却时间，树有半径。若敌人在巫师的攻击范围外，或者巫师和敌人之间被树挡着&#xff0c…

JSOI2014第三轮 DAY2T2 士兵部署

// 完全搞不懂版权到底是个什么东西..不过如果内容侵犯版权的话请提醒我删除A 题目大意： 给你若n个士兵，对于一个点，如果从该点出发，朝任意一个方向移动，都会和至少一个士兵的距离减少，则称这个点是可以被…

【HNOI2016模拟4.4】Stage

Description N,M<1e3 Solution 考虑每个点被观察到的概率这样很难算我们可以计算每个点不被观察到的概率这个等价于把这个点和所有观察点拉出来一起做凸包，这个点出现在凸包上的概率那么我们可以枚举两条边，计算这两条边出现的概率就是这两…

POJ 3384 Feng Shui 风水（半平面交求可以放入的两个相同圆的最大面积）

传送门:POJ 3384 题意：将两个半径为 r 的圆放入一个多边形中，两圆可以重叠，问两个圆占据最大面积时圆心坐标是多少，可以转化为求可以放入多边形中的最大圆的半径问题解决。前置技能：半平面交求解多边形中可以放入的最…

【WinterCamp 2013】数三角形

Description 给出二维平面上的n个点，求这n个点形成的三角形中，有多少个三角形包含原点。 n<1e5,坐标绝对值<1e5 Solution 第一道计算几何留影_ (:з」∠) _ 首先我们将这n个点按与x轴正半轴的夹角从小到大排序然后我们统计每个点往右能形成…

2019牛客暑期多校训练营（第五场）I three points 1（计算几何+思维）

链接：https://ac.nowcoder.com/acm/contest/885/I 题意：T组样例，给你w、h、a、b、c。让你按顺序输出3个坐标X、Y、Z，其中X、Y的距离是a，X、Z的距离是b，Y、Z的距离是c。并且这3个点x坐标要在[0，…

【数学】【计算几何】1453. 圆形靶内的最大飞镖数量

作者推荐视频算法专题本文涉及知识点数学计算几何 LeetCoce:1453. 圆形靶内的最大飞镖数量 Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。 Bob 知道墙上所有 n 支飞…

Qt实现三次样条Cardinal曲线

目录 1. 前言 2. 预备知识 3. 代码实现 1. 前言在设计矢量图案的时候，我们常常需要用到曲线来表达物体造型，单纯用鼠标轨迹绘制显然是不足的。于是我们希望能够实现这样的方法：通过设计师手工选择控制点，再通过插值得到过控制…

二，几何相交---4，BO算法---（1）接近性和可分离性

提了三个观点 1，如果一条直线（比如竖直）可以分开两个线段，则这两个线段不相交 2，只需要观察与隔离线相交的几个线段 3，从左向右扫描线只需要观察每个线段的两个端点和一些可能的相交点。

codeforces 994C Two Squares

题目大意：给你两个正方形，一个平行于坐标轴，一个与坐标轴成45角，判断是否相交坐标范围 （-100 ，100） 题解：一开始觉得这个判断很复杂，然后发现坐标范围很小&#xff0c…

//凸包///int ConvexHull(Point *p,int n,Point* ch) { //返回凸包顶点数，凸包顶点存在ch中sort(p,pn);int m0;for(int i0; i<n; i) {while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0)m--;ch[m]p[i];}int km;for(int in-2; i>0; i--) {while…

圆的反演 hdu 6097

欢迎关注更多精彩关注我，学习常用算法与数据结构，一题多解，降维打击。题目大意 http://acm.hdu.edu.cn/showproblem.php?pid6097 有一个圆C，它的圆心是O(0,0), 半径是r。在C内部或边界上有两点P和Q，OPOQ。求解…

计算几何+2sat：1020T3

http://cplusoj.com/d/senior/p/SS231019C 我们进行这样的转化则0/1必选一个，2/3必选一个那么就变成一个2sat问题两三角形有交，则一个选，一个不能选对角三角形一个选，一个不选。一个不选，一个选三角形不合法…

南阳理工学院OJ - 0003 - 多边形重心问题

题目要求我们给出按顺序给出的N点组成的多边形的面积和重心横纵坐标的和，考查计算几何。我们有任意N边形的有向面积计算公式： S′∑i1n−1(xi−x0)(yi1−y0)−(yi−y0)(xi1−x0)2记按顺序排列的连续两点与选取某一点的三角形的有向面积： S…

第一个计算几何算法的可视化---极点法获取凸包

生成随机的点使用EP算法得到极点初始化状态3重循环遍历三角形第四重循环判断点intriagle测试里面先要保证三角形的顶点是CCWto-left测试的计算公式可视化所有的点完整代码 import pygame import random# 定义颜色 RED (255, 0, 0) GREEN (0, 255, 0) BACKGROUND_COLOR…

bzoj 1043: [HAOI2008]下落的圆盘

Description 有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求. Input n ri xi y1 ... rn xn yn Output 最后的周长，保留三位小数 Sample Input 2 1 0 0 1 1 0Sample Output 10…

【GDOI2018模拟7.7】寻找天哥

Description n<3000 Solution 答案相当于求E(∫R04π3x3dx)也就是求E(π3R4)现在就是要找到一种方法求E(R4)发现这个东西等价于求E(((∑i1naixi)2(∑i1nbixi)2(∑i1ncixi)2)2)其中xi是一个在[0,1]范围内均匀分布的实数设∑ni1aixiA,∑ni1bixiB,∑ni1cixiC那么答案就是E(A…

POJ 3130 How I Mathematician Wonder What You Are! 3335 Rotating Scoreboard （半平面交求多边形的核）

传送门： 1.POJ 3335 2.POJ 3130 前置技能： 1.半平面交判断多边形核是否存在，请移步我的博客：半平面交算法原理及应用的讲解。 2.reverse函数，用于将数组中的元素颠倒位置。题目大意：其问题都是判断多…

【运筹优化】凸多面体重叠判断算法：GJK 算法详解 C++代码实现二维情形的凸多边形重叠判断

文章目录一、GJK 算法简介二、前置知识2.1 二维向量的点乘和叉乘2.2 三维向量叉乘2.3 凸多边形2.4 闵可夫斯基差2.5 单纯形2.6 Support 函数三、GJK 算法讲解3.1 熟悉 GJK 算法流程3.1.1 多边形重叠的情形3.1.2 多边形不重叠的情形3.2 总结 GJK 算法步骤3.3 讲解 GJK 算法细节3…

[CF886F]Symmetric Projections

Description 给出二维平面上的n个点，求有多少条经过原点的直线满足，所有点在其上的投影是对称的。若有无数条输出-1 n<2000 Solution 根据一些脑洞结论我们知道对称中心一定是原点集的重心在直线上的投影如果两个点关于重心中心对称那么这两个…

bzoj 1502: [NOI2005]月下柠檬树

Description Input 文件的第1行包含一个整数n和一个实数alpha，表示柠檬树的层数和月亮的光线与地面夹角(单位为弧度)。第2行包含n1个实数h0,h1,h2,…,hn，表示树离地的高度和每层的高度。第3行包含n个实数r1,r2,…,rn，表示柠檬树每层下底面的圆…

bzoj 2178: 圆的面积并

Description 给出N个圆，求其面积并Input 先给一个数字N ,N< 1000 接下来是N行是圆的圆心，半径，其绝对值均为小于1000的整数Output 面积并，保留三位小数自适应辛普森。。留个模板好了#include<cmath> #include<cstdio…

【GDOI2013模拟1】屏保

Description 平面直角坐标系内有n个点，第i个点的坐标为(i,Hi)，顺次连接这n个点。现在给出一条直线yh，求这条直线以下的由这条直线和其他线段围成的图形的面积。兹瓷单点修改。 n<10^5,hi<1000 语文不好，放图来讲讲道…

计算几何之半平面交算法模板及应用

欢迎关注我的个人博客：www.zuzhiang.cn 自己在学习半平面交的时候看到网上有几张图片很不错就 down 下来在本文中使用了……如果博主大大不乐意请联系我删除。下面给出两个我觉得不错的博客： 1.半平面交讲解1 2.半平面交讲解2 定义： 半平面…

FZU 1015 土地划分（计算几何求线段交点个数）

传送门：FZU 1015 题目大意：求 L 条头尾相连的线段将矩形分成多少块。注意每个线段的端点都在矩形的边上，且不会有3线共点。前置技能：计算几何判断两线段是否相交。这个直接套用模板就可以了。其思想是如果以两条线段为对角线的两…

[LOJ6360]复燃「恋之埋火」

Description 古明地恋(koishi)和小石子(koishi)是好朋友。旧地狱的空中散布着许多颗小石子。恋恋想找出一个位置，使得这个位置离最远的小石子的距离尽可能小。需要注意的是，这里的空间可能是高维空间。 “在这幻想乡里，可不能被常理所…

2018 BUPT Winter Training #6 Div.2

A - Intersecting Lines rt,求相交直线。 #include <iostream> #include <cstdlib> #include <cmath> #include <iomanip> #define FF(_i,_l,_r) for(int _i_l;_i<(_r);_i) using namespace std; const double eps 1e-6; struct Point {double x…

Codeforces #488div.2 - 994C - Two Squares(计算几何入门)

第一个也是很简单就容易判断的是：两个线段一旦相交就一定是YES 然后就是判断不相交但是也是YES的情况了，我们可以这样思考： 依照题意，正方形的点是按时钟顺序给出的，那么在正方形中的点就一定会被头尾依次相连的四个…

GAMES101笔记 Lecture 01

目录 Overview of Computer Graphics图形学的应用场景Video GamesMoviesAnimationsDesignVisualizationVirtual RealityDigital IllustrationSimulationGraphical User InterfacesTypography 为什么要学习计算机图形学？Fundamental Intellectual Challenges(图形学很…

[NOIP2001 提高组] Car 的旅行路线（C++，计算几何）

题目描述又到暑假了，住在城市 A 的 Car 想和朋友一起去城市旅游。她知道每个城市都有 444 个飞机场，分别位于一个矩形的 444 个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第 iii 个城市中高速铁路的单位里程价格为…

平行六面体的体积

如图：Sb,c∣BC∣S_{b,c}|B\times C|Sb,c∣BC∣设uuu是HHH的方向向量HAuHA\times uHAu 有右手定则得uuu是B,CB,CB,C的方向向量uBC∣BC∣u\frac{B\times C}{|B\times C|}u∣BC∣BC SSb,c∗HSb,c∗(Au)∣BC∣∗ABC∣BC∣ABCSS_{b,c}*HS_{b,c}*(A\times u)|B\times …

半平面求交

• Step 1: Separate the h-planes into two sets. One has polar angles of (-π, π], the other has those of (-π, -π]∪(π, π]. • 将半平面分成两部分，一部分极角范围(-π, π]，另一部分范围(-π, -π]∪(π, π] 。 Step 2: Consider the se…

【题解】洛谷 P9658 Laser Trap

题解-P9658 Laser Trap 题目传送门题意简述题面是英文的，还没翻译，就讲一讲吧。 n n n 个激光发射器，两两之间产生激光束，将平面分为若干区域。问至少删去多少个发射器，可以使得原点与外侧区域联通。多组数据&a…

$HDU 2036（求任意多边形的面积）$

HDU 2036（求任意多边形的面积）

“ 改革春风吹满地, 不会AC没关系; 实在不行回老家， 还有一亩三分地。谢谢!（乐队奏乐）” 话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来…