acm-计算几何模板
#include
using namespace std;
const double eps =1e-8;
const double INF =1e20;
const double pi = acos ;
int dcmp (double x) {
if (fabs (x) < eps) return0;
return (x <0-1:1);
》
}
inline double sqr (double x) {return x*x;}
f %.2f\n", x, y);}
bool operator== (const Point &b) const {
return (dcmp ==0&& dcmp ==0);
}
bool operator< (const Point &b) const {
return (dcmp ==0 dcmp <0: x < ;
}
；
Point operator+ (const Point &b) const {
return Point (x+, y+;
}
Point operator- (const Point &b) const {
return Point , ;
}
Point operator* (double a) {
return Point (x*a, y*a);
}
Point operator/ (double a) {
`
return Point (x/a, y/a);
}
double len2 () {f\n", r);
}
bool operator== (const Circle &a) const {
return p ==&& (dcmp ==0);
}
double area () {otate_left ());
Line v = Line ((b+c)/2, ((b+c)/2) + (c-b).rotate_left ()); Point p = line_intersection (u, v);
]
double r = dis (p, a);
return Circle (p, r);
}
Circle in_circle (Point a, Point b, Point c) { r -l*l);
Point tmp =+ (l);
p1 = tmp + ( ().change_len (h));
p2 = tmp + ( ().change_len (h));
if (rel ==2|| rel ==4) return1;
return2;
~
}
int line_cirlce_intersection (Line v, Circle u, Point &p1, Point &p2) {hange_len (r1));
= q + ( ().change_len (r1));
== r1;
return2;
}
Line u1 = Line + ().change_len (r1), + ().change_len (r1)); Line u2 = Line + ().change_len (r1), + ().change_len (r1)); Circle cc = Circle (q, r1);
.
Point p1, p2;
if (!line_cirlce_intersection (u1, cc, p1, p2))
line_cirlce_intersection (u2, cc, p1, p2);
c1 = Circle (p1, r1);
if (p1 == p2) {
c2 = c1;
return1;
}
c2 = Circle (p2, r1);
return2;
、
}
int get_circle (Line u, Line v, double r1, Circle &c1, Circle &c2, Circle &c3, Circle &c4) {hange_len (r1), + ().change_len (r1));
Line u2 = Line + ().change_len (r1), + ().change_len (r1)); Line v1 = Line + ().change_len (r1), + ().change_len (r1)); Line v2 = Line + ().change_len (r1), + ().change_len (r1));
==== r1;
= line_intersection (u1, v1);
= line_intersection (u1, v2);
= line_intersection (u2, v1);
#
= line_intersection (u2, v2);
return4;
}
int get_circle (Circle cx, Circle cy, double r1, Circle &c1, Circle &c2) {otate_left ());
v = u;
return1;
}
double d = dis , q);
double l =*d;
。
double h = sqrt *- l*l);
u = Line (q, + .change_len (l) + .rotate_left ().change_len (h)); v = Line (q, + .change_len (l) + .rotate_right ().change_len (h));
return2;
}
double area_circle (Circle a, Circle v) {" << endl;
return res;
}
-
- ;
int d2 = dcmp (b[(i+1)%n].y - ;
if (k >0&& d1 <=0&& d2 >0)
w++;
if (k <0&& d2 <=0&& d1 >0)
w--;
}
if (w !=0)
return1;
return0;
·
}
int convex_cut (Line u, Point *p, int n, Point *po) {//直线切割多边形左侧
//返回切割后多边形的数量
int top =0;
for (int i =0; i < n; i++) {
int d1 = dcmp (cross p[i]);
int d2 = dcmp (cross p[(i+1)%n]);
if (d1 >=0) po[top++] = p[i];
if (d1*d2 <0) po[top++] = line_intersection (u, Line (p[i], p[(i+1)%n]));
（
}
return top;
}
double convex_circumference (Point *p, int n) {//多边形的周长(凹凸都可以)
double ans =0;
for (int i =0; i < n; i++) {
ans += dis (p[i], p[(i+1)%n]);
}
return ans;
@
}
double area_polygon_circle (Circle c, Point *p, int n) {//多边形和圆交面积
double ans =0;
for (int i =0; i < n; i++) {
int j = (i+1)%n; //cout << i << " " << j << "//" << endl;
if (dcmp (cross (p[j], p[i]) >=0)
ans += circle_traingle_area (p[i], p[j], c);
else
ans -= circle_traingle_area (p[i], p[j], c);
、
}
return fabs (ans);
}
Point centre_of_gravity (Point *p, int n) {//多边形的重心(凹凸都可以) double sum = , sumx =0, sumy =0;
Point p1 = p[0], p2 = p[1], p3;
for (int i =2; i <= n-1; i++) {
p3 = p[i];
double area = cross (p2-p1, p3-p2)/;
~
sum += area;
sumx +=++*area;
sumy +=++*area;
p2 = p3;
}
return Point (sumx/*sum), sumy/*sum));
}
int convex_hull (Point *p, Point *ch, int n) {//求凸包
//所有的点集凸包点集点集的点数
！
sort (p, p+n);
int m =0;
for (int i =0; i < n; i++) {
while (m >1&& cross (ch[m-1]-ch[m-2], p[i]-ch[m-1]) <=0) m--;
ch[m++] = p[i];
}
int k = m;
for (int i = n-2; i >=0; i--) {
while (m > k && cross (ch[m-1]-ch[m-2], p[i]-ch[m-1]) <=0) m--;
ch[m++] = p[i];
}
if (n >1)
m--;
return m;
}