Spy97

计算几何

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 贪心(2)

/ 注册

全部文章 / 计算几何（共30篇）

codeforces 933C

题意：给出三个点，求将二维平面划分成几部分。题解：感谢quailty的出题以及题解。首先是常规的欧拉公式：其中,表示划分成的平面数，为边数（edge），为顶点数（vertices）。这里，将其进行变形。表示整个图形的圆弧数，对单个圆来说，等于圆的上的交点数，求和即可求出，表...

2018-07-28

0 422

codeforces 982E

题解：先单独处理水平和竖直走的情况，在分析斜着走的情况。每次我们遇到边界，不反弹，而是接着走，理解为地图向前进的两个方向翻转扩展，直到走到了四个角落之一，算出两个方向各自扩展的数量，在根据奇偶来确定坐标。利用扩展欧几里得来算出是否有解。代码： #include<bits...

2018-07-28

0 457

Nested Triangles 2018 ACM-ICPC中国大学生程序设计竞赛

题目链接：https://nanti.jisuanke.com/t/28410 题目大意：给出n个点，和两个点P，Q，求一个最大的集合，使得集合中的点与P、Q两点围成的三角形是层层包含的，若有多种最大数目的方案，输出字典序最小的。题解：设n个点为点c[i]，首先将n个点依据直线PQ的两...

2018-07-19

0 440

CSU 2212 Particle Collision

Description Particle colliders are difficult to build and experiments are costly to run. Before running any real experiments it is better to do a sim...

2018-06-01

0 423

Codeforce 975E

E. Hag's Khashba time limit per test 3 seconds memory limit per test 256 megabytes input standard input ...

2018-05-17

0 390

HDU 1589

模板题，给出一些点，求两点间最近和最远距离。代码： #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <cmath&...

计算几何最近点对最远点对

2018-04-21

0 480

CSU 2068 pacnw2012

2068: Ritual Circle Submit Page Summary Time Limit: 60 Sec Memory Limit: 512 Mb Submitted: 2 Solved: 1 Descript...

计算几何暴力

2018-04-21

0 381

CSU 2029 ATRC 2017

2029: Border Wall Submit Page Summary Time Limit: 3 Sec Memory Limit: 512 Mb Submitted: 2 Solved: 1 Description...

2018-04-09

0 517

ICPC 2017 北京 Liaoning Ship’s Voyage

题目地址：http://hihocoder.com/problemset/problem/1633?sid=1234017 题目大意：在二维平面内，船从(0,0)出发到(n-1,n-1)结束，求最短路，要求：一个点可以向周围8个方向走，距离都为1，并告诉哪些点不可以走，同时要求路线不可以穿过...

2017-11-19

0 508

ICPC 2017 青岛 Spacecraft

题目地址：https://nanti.jisuanke.com/t/18518 人生第一篇博客。。。用两个向量face和head模拟人的方位，向上或向下旋转ang角时，两个向量都旋转ang角，左右旋转时，face旋转ang角，head不变，自己感受一下就知道了。主要就是两个模板，三...

2017-11-13

0 448