POJ 3335 Rotating Scoreboard (半平面交)
显然如果对所有墙壁求半平面交结果不是 0 的话就是 YES，否则就是 NO 。 另外数据中点是顺时针给出的，题里貌似没有说明。。 #include <stdio.h>#include <string.h>#include <iostream>#include &...
半平面交模板(BZOJ1007)
#include<cstdio>#include<algorithm>#define LDB long doubleusing namespace std; int ans[]; struct lin{ LDB k,b; int num; }a[];...
洛谷P3222 [HNOI2012]射箭（计算几何，半平面交，双端队列）
洛谷题目传送门设抛物线方程为\(y=ax^2+bx(a<0,b>0)\)，我们想要求出一组\(a,b\)使得它尽可能满足更多的要求。这个显然可以二分答案。如何check当前的\(mid\)是否合法呢？每一个限制条件形如\(y_{i_1}\le ax_i^2+bx_i\le y_{i_2}...
POJ 3384 放地毯【半平面交】
<题目链接>题目大意：给出一个凸多边形的房间，根据风水要求，把两个圆形地毯铺在房间里，不能折叠，不能切割，可以重叠。问最多能覆盖多大空间，输出两个地毯的圆心坐标。多组解输出其中一个，题目保证至少可以放入一个圆。解题分析：因为放置的圆不能超出多边形的边界，所以先将该凸多边形的各个边长向内平...
POJ3335 POJ3130 POJ1474 [半平面交]
终于写出自己的半平面交模板了.......加入交点的地方用了直线线段相交判定三个题一样，能从任何地方看到就是多边形的内核只不过一个顺时针一个逆时针(给出一个多边形的两种方式啦)，反正那个CutPolygon是切掉左面只要穿参数时换一下就好了第三题卡输出啊啊啊啊啊#include <iostre...
POJ 3525 Most Distant Point from the Sea （半平面交+二分）
MostDistantPointfromtheSeaTimeLimit: 5000MS MemoryLimit: 65536KTotalSubmissions: 3476 Accepted: 1596 SpecialJudgeDescriptionThemainlandofJapancalledHo...
poj2540Hotter Colder(半平面交）
链接根据距离可以列得直线方程，附上初始矩形的四个顶点，依次用直线切割。#include<iostream>#include<stdio.h>#include<math.h>#include<cstring>#include<algorithm&g...
poj 1279 -- Art Gallery （半平面交）
鏈接：http://poj.org/problem?id=1279ArtGalleryTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 5337 Accepted: 2277DescriptionTheartgalleriesofthene...
POJ3525 Most Distant Point from the Sea(半平面交)
给你一个凸多边形，问在里面距离凸边形最远的点。方法就是二分这个距离，然后将对应的半平面沿着法向平移这个距离，然后判断是否交集为空，为空说明这个距离太大了，否则太小了，二分即可。#pragmawarning(disable:4996)#include<iostream>#include&l...
poj 3335（半平面交）
链接：http://poj.org/problem?id=3335 //大牛们常说的测模板题----------------------------------------------------------------RotatingScoreboardTimeLimit: 2000MS Mem...
POJ 3384 Feng Shui 半平面交
题目大意：一个人很信“FengShui”，他要在房间里放两个圆形的地毯。这两个地毯之间可以重叠，可是不能折叠，也不能伸到房间的外面。求这两个地毯可以覆盖的最大范围。并输出这两个地毯的圆心。思路：我们当然希望这两个圆形的地毯离得尽量的远，这种话两个圆之间的重叠区域就会越小，总的覆盖区域就越大。那我们就...
Luogu3297 SDOI2013逃考（半平面交+最短路）
把每个人的监视范围看成点，相邻的两个监视范围连边，那么跑一遍最短路就可以了（事实上边权都为1可以直接bfs）。显然存在最优路线没有某个时刻同时被多于两人监视，要到达另一个区域的话完全可以经过分界线而不是和其他区域的交点（若两个区域只有一个交点的话是不能直接到达的），总之就是说不用特判同时被多人监视的...