我是一头猪啊ฅ

分类

未归档(113)

/ 注册

全部文章（共113篇）

bzoj 1207: [HNOI2004]打鼹鼠

看似n^2暴力其实第二个循环是1~n递增的而且常熟极小就跑过了 /************************************************************** Problem: 1207 User: lxy8584099 L...

dp

2019-02-25

0 498

bzoj 1202: [HNOI2005]狡猾的商人

dfs找负环（或者spfa） #include<cstdio> #include<cstring> using namespace std; const int N=150,M=1500; struct pp { int v,nxt,d; } e[M&...

差分约束

2019-02-25

0 423

bzoj 1941: [Sdoi2010]Hide and Seek

KD_tree的估价查询 /************************************************************** Problem: 1941 User: lxy8584099 Language: C++ Resul...

KD_tree

2019-02-24

0 495

POJ 1474 Video Surveillance

只需要判断就行了不需要正宗的半平面交 /* Point operator & (Line A,Line B) { Point C=A.s; double t=((A.s-B.s)^(B.s-B.e))/((A.s-A.e)^(B.s-B.e)); C...

计算几何半平面交

2019-02-23

0 541

POJ 2954 Triangle

Pick定理万岁！！！ /* 2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。这样求出三角形面积求出边上的点内部的点就呼之欲出了！ */ #include<cstdio> using namespace std; long l...

乱搞

2019-02-22

0 512

POJ 1654 Area

计算多边形面积的通式 /* 不规则多边形的计算通过容斥三角形得到答案 */ #include<cstdio> #include<cstring> #define ll long long using namespace std; const int N=1e6+50...

计算几何

2019-02-22

0 368

POJ 3348 Cows

简单的求凸多边形面积求不规则多边形也是类似只要选择的点是沿着多边形边选就行了通过容斥会得到正确答案 #include<cmath> #include<cstdio> #include<algorithm> #define db double...

计算几何

2019-02-22

0 414

POJ 1113 Wall

由图可知路径长度就是图包+一个以L为半径的圆四舍五入很玄学。。。 /* 取一个最第点极角排序类似单调队列地删点 */ #include<cmath> #include<cstdio> #include<algorithm> using n...

计算几何

2019-02-22

0 403

POJ 1696 Space Ant

数据小暴力极角排序先把最下面的一个点放在第一位这样乃至以后的计算极角都是在0～Pi 范围内的每次排序后的第一个点一定是最优的 /* 首先一定能把所有点都走完其次是如何走我们先选择一个x最小的开始每次走到了v 就以v为极点对于剩余的点进行极角排序选择极角最小的点走 *...

计算几何

2019-02-22

0 484

POJ 2653 Pick-up sticks

线段相交判断 /* 链表维护 n^2算法? */ #include<cstdio> #include<algorithm> using namespace std; const int N=1e5+50; const double eps=1e-9; ...

计算几何

2019-02-22

0 395