计算几何 – Tgotp-Blog

1670: [Usaco2006 Oct]Building the Moat护城河的挖掘

裸的凸包,直接造一个凸包,然后算一下长度就好了

c++代码如下:

 

2338: [HNOI2011]数矩形

计算几何。。。

c++代码如下:

 

B. Tell Your World

B. Tell Your World
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard o[......]

Read more

1069: [SCOI2007]最大土地面积

第一次做旋转卡壳,但是还有一点是...用vim写的,然后写了贼久...逐渐熟悉这玩意吧...

基本就是按照黄学长的blog打的,没什么变动...因为自己太弱.

c++代码如下:

 

P1034 矩形覆盖

被题意坑了,应该是该怎么做就怎么做

主要思路在于:因为分为k份,所以对应每个点一定会被分到某个集合内,所以枚举一下就好了。

然后再判一下交线交点,就搞定了,挺简单。

dfs回溯

c++代码如下:

 [......]

Read more

BZOJ 1041: [HAOI2008]圆上的整点

首先只考虑x,y均为正数的情况,最后答案*4即可

如果在圆的边界上一定会满足:r^2 = x^2 + y^2

化简 (r - x ) * (r +x ) = y^2

令 z = gcd(r - x ,r + x), u = (r+x) / z,v = (r-x)/z     (u[......]

Read more

水平可见直线 BZOJ 1007 && 洛谷 3194

类型:半平面交

注意:初始情况下 应直接压入;

实现:直接手推 y 相同时 x的情况,进行更新(建议自己过手推一遍)。

算法:排序和单调栈

c++代码如下: