beckyUp

计算几何

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 动态规划(18) 区间dp(3) 博弈(2) 后缀数组(1) 图论(8) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数据结构(22) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算方法(4) 读书笔记(2)

/ 注册

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

2017北京区域赛 G - Liaoning Ship’s Voyage【计算几何+bfs】

题目大意：一个图上有n*n个点，然后从起点走到终点，然后需要绕过三角形和“#”，问一个最短路径分析：由于边上的点和端点都是能走的，我在扩展边的时候，判断该边与三角形是否有焦点，我原先是判断线段与线段的交点，然后判断点是否在三角形内部，后来发现如果一个线段的起点和终点都不在三角形内部的话，也是有可能...

2018-10-06

0 426

计算几何基础 Intersection POJ - 1410

这个题判断线段和矩形的相交情况注意线段在矩形内部的情况 #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstrin...

2018-09-12

0 309

计算几何基础 Treasure Hunt POJ - 1066【线段相交】

这个思路确实没有想到，直接把每个点和终点连起来看与线段相交的个数就可以了？注意n=0的情况 #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #...

2018-09-12

0 323

计算几何基础 POJ - 1556 The Doors【抠关键点求最短路】

#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <queue> us...

2018-09-11

0 259

计算几何基础 POJ 1269 Intersecting Lines 【直线相交判断，求交点】

#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int maxn=1e5+50; const ...

2018-09-11

0 455