CodeForces 166B – Polygons [凸包]


Link http://codeforces.com/problemset/problem/166/B Mean 给两个多边形,保证第一个为凸多边形。多边形三点不共线。问你第二个多边形是否在第一个多边形内部,也即所有点都在第一个多边形内部。 Analysis 求第一个多边形的凸包和两个多边形公共凸包,判断两个凸包...

CodeForces 166B – Polygons [凸包]

Link http://codeforces.com/problemset/problem/166/B Mean 给两个多边形,保证第一个为凸多边形。多边形三点不共线。问你第二个多边形是否在第一个多边形内...
阅读全文 0

HDU 4491 – Windmill Animation [几何]


Link 传送门 Problem A windmill animation works as follows: A two-dimensional set of points, no three of which lie on a line is chosen. Then one of the points is chosen (as the first pivot) and a line is drawn through the chosen point at some initi...

HDU 4491 – Windmill Animation [几何]

Link 传送门 Problem A windmill animation works as follows: A two-dimensional set of points, no three of which lie on a line is chosen. Then one of ...
阅读全文 0

POJ 2954 – Triangle [几何/Pick定理]


Link 传送门 Problem A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie complet...

POJ 2954 – Triangle [几何/Pick定理]

Link 传送门 Problem A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle ...
阅读全文 0

UVa 10535 – Shooter [贪心+几何]


Link 传送门 Problem The shooter is in a great problem. He is trapped in a “2D” maze with a laser gun and can use it once. The gun is very powerful and the laser ray, it emanates can traverse infinite distance in its direction. In the maze the targ...

UVa 10535 – Shooter [贪心+几何]

Link 传送门 Problem The shooter is in a great problem. He is trapped in a “2D” maze with a laser gun and can use it once. The gun is very powerful ...
阅读全文 0

POJ 2002 – Squares [几何+二分]


Link 点击打开poj题目链接 Problem A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the onl...

POJ 2002 – Squares [几何+二分]

Link 点击打开poj题目链接 Problem A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a...
阅读全文 0

HDU 2438 – Turn the corner [几何+暴力/三分法]


Link 点击打开hdu题目链接 Mean 有一辆车要拐过一个拐角路口,给你两条路的宽度和车的长和宽,问你能不功能成功拐过路口。 Analyse 这道题是个人赛上的,经过长春区域赛打铁的教训,不会做就暴力啊!!!果真就又爆过去了,没有用三分。 就是假定车沿着右下角拐着走...

HDU 2438 – Turn the corner [几何+暴力/三分法]

Link 点击打开hdu题目链接 Mean 有一辆车要拐过一个拐角路口,给你两条路的宽度和车的长和宽,问你能不功能成功拐过路口。 Analyse 这道题是个人赛上的,经过...
阅读全文 0

ZOJ 3728 – Collision [几何]


点击打开zoj题目链接 题意 题目的题意不太好理解,建议多读几遍画画图。就是在一个大圆内有一个小圆形的奖牌,圆心在原点。然后有一个圆形的小硬币,它有一个起始点和一个移动速度,这个硬币碰到奖牌会反弹。问你硬币运动过程中在奖牌内的时间是多少。 分析 硬币是有...

ZOJ 3728 – Collision [几何]

点击打开zoj题目链接 题意 题目的题意不太好理解,建议多读几遍画画图。就是在一个大圆内有一个小圆形的奖牌,圆心在原点。然后有一个圆形的小硬币,它有一个...
阅读全文 0

HDU 5017 – Ellipsoid [几何+模拟退火]


点击打开HDU题目链接 题意:给一个椭球的一般式方程,然后求原点到球上一点的最短距离。 分析:模拟退火逐步取得最优值,三分套二分之类的可能会退公式麻烦一些。下面是跟网上学的模拟退火算法做的。 #include <bits/stdc++.h> using namespace std; con...

HDU 5017 – Ellipsoid [几何+模拟退火]

点击打开HDU题目链接 题意:给一个椭球的一般式方程,然后求原点到球上一点的最短距离。 分析:模拟退火逐步取得最优值,三分套二分之类的可能会退公式麻烦一...
阅读全文 0

UVa 1643 – Angle and Squares [几何]


点击打开vjudge题目链接 题意:在坐标系第一象限给一个定点在原点的角,然后给定n个正方形,问怎样在这个角里放正方形才使得左边阴影部分面积最大。 分析:画画图可以发现当这些正方形的对角线连成一条直线的时候阴影面积最大。然后推出公式即可。 下面代码可以作为...

UVa 1643 – Angle and Squares [几何]

点击打开vjudge题目链接 题意:在坐标系第一象限给一个定点在原点的角,然后给定n个正方形,问怎样在这个角里放正方形才使得左边阴影部分面积最大。 分析:画...
阅读全文 0

向量叉积的应用(三角形面积,线段相交,多边形面积,多边形凹凸性)


向量叉积有甚多应用,包括求三角形面积,判断线段相交,求多边形面积,判断多边形凹凸性,而且不需要推大量公式,误差较小,非常实用,下面是代码 //向量叉积的应用 #include <bits/stdc++.h> #define EPS 1e-10 using namespace std; struct point{ ...

向量叉积的应用(三角形面积,线段相交,多边形面积,多边形凹凸性)

向量叉积有甚多应用,包括求三角形面积,判断线段相交,求多边形面积,判断多边形凹凸性,而且不需要推大量公式,误差较小,非常实用,下面是代码 //向量叉...
阅读全文 1