我是一头猪啊ฅ

分类

未归档(113)

/ 注册

全部文章（共10篇）

bzoj 1027: [JSOI2007]合金

好多特判。。。（我只写了一个）凸包+Floyd 还学到了怎么判断点线位置 /* 万万没想到是个几何题首先 z是没用的因为x，y确定了那么z就确定了 x，y看做笛卡尔坐标要是一个东西能被两个东西合成那么一定在两个东西的连线上如果是...

计算几何凸包

2018-12-27

0 457

POJ 2318 TOYS

入门第一发了解点，向量的表示学会判断点与直线的位置关系 /* 输入文件包含一个或多个问题，第一行是第一个问题包含6个数，n,m,x1,x2,y1,y2,纸板分区的数目为n （0 < n <= 5000），玩具的数量是m（0＜m＜5000），箱子左上角的坐标为（x1,y1），...

计算几何

2019-02-22

0 487

POJ 3304 Segments

注意判断大于小于等于0的时候要用eps 而不是用0 见cross相乘判断用0即WA /* 尝试向量，点都用Point表示 */ #include<cmath> #include<cstdio> #include<cstring> #...

计算几何

2019-02-22

0 529

Uva 378 Intersecting Lines

题目与POJ 1269 相同不过POJ一直WA 新的姿势求两直线的交点 a,b,c,d c1=cross(a,b,c),c2=cross(a,b,d) x=(c2*c.x-c1*d.x)/(c2-c1) y=(c2*c.y-c1*d.y)/(c2-c1) (c2...

计算几何

2019-02-22

0 650

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

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 3348 Cows

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

计算几何

2019-02-22

0 414

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 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