计算几何
CCDV2
7月 09, 2018
线段
线段是对两个点的操作。。
重载运算符，求交点等等。。const double EPS = 1e-6; struct Point { Point() {} Point(double _x, double _y): x(_x), y(_y) {} double getDis(Point rhs) { double xx = rhs.x - x, yy = rhs.y - y; return sqrt(xx * xx + yy * yy); } void input(){scanf("%lf%lf", &x, &y);} double x, y; }; double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;} Point operator +(Point lhs, Point rhs){return Point(lhs.x + rhs.x, lhs.y + rhs.y);} Point operator -(Point lhs, Point rhs){return Point(lhs.x - rhs.x, lhs.y - rhs.y);} Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);} Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);} double operator *(Point lhs, Point rhs){return lhs.x * rhs.x + lhs.y * rhs.y;} bool isCross(Point &a, Point &b, Point &c, Point &d)//线段是否相交 { if(min(a.x, b.x) <= max(c.x, d.x) && min(a.y, b.y) <= max(c.y, d.y) && min(c.x, d.x) <= max(a.x, b.x) && min(c.y, d.y) <= max(a.y, b.y)) { double u, v, w, z; u = (c - a) ^ (b - a); v = (d - a) ^ (b - a); w = (a - c) ^ (d - c); z = (b - c) ^ (d - c); if(u * v <= EPS && w * z <= EPS) return true; } return false; } Point getIntersect(Point &a, Point &b, Point &c, Point &d)//在相交的前提下求交点 { double D = (a - b) ^ (c - d); double a1 = b.y - a.y, a2 = d.y - c.y; double b1 = a.x - b.x, b2 = c.x - d.x; double c1 = a ^ (b - a), c2 = c ^ (d - c); Point ret = Point((b2 * c1 - b1 * c2) / D, (a1 * c2 - a2 * c1) / D); return ret; }相关例题
极角
第一种方法：向量int quadrant(Point t) { if(t.x > 0 && t.y >= 0) return 1; if(t.x <= 0 && t.y > 0) return 2; if(t.x < 0 && t.y <= 0) return 3; if(t.x >= 0 && t.y < 0) return 4; if(t.x == 0 && t.y == 0) return 0; perror("!!error"); printf("%lf %lf\n", t.x, t.y); return -1; } bool cmp(Point &a, Point &b)//这里的a, b均是向量 { int qa = quadrant(a), qb = quadrant(b); if(qa == qb) { return (a ^ b) < EPS; } return qa < qb; }第二种方法：
atan2(double y, double x);-pi ~ pi
相关例题
没做出来。。算了
圆
一个点+半径相关例题
凸包
需要用到极角排序。相关例题
poj1228 稳定凸包
poj1584 多边形是否为凸包+点是否在多边形内+圆是否能放到凸包内
poj1873 求凸包模板在这里！
poj2540 求多边形面积+半平面切割多边形
uva4426m 质心
cf1017E 两个凸包是否同构- 扫描线
需要排序+线段树。。相关例题
- 半平面
相关例题
- 旋转卡壳
听说旋转卡壳能解决很多问题。。相关例题
- 分治法
相关例题