• // 计算几何模板 const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const int maxp = 1010; //Compares a double to zero int sgn(double x){ if(fabs(x) < eps)re...

二维几何
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}
/*
* Point
* Point()               - Empty constructor
* Point(double _x,double _y)  - constructor
* input()             - double input
* output()            - %.2f output
* operator ==         - compares x and y
* operator <          - compares first by x, then by y
* operator -          - return new Point after subtracting curresponging x and y
* operator ^          - cross product of 2d points
* operator *          - dot product
* len()               - gives length from origin
* len2()              - gives square of length from origin
* distance(Point p)   - gives distance from p
* operator + Point b  - returns new Point after adding curresponging x and y
* operator * double k - returns new Point after multiplieing x and y by k
* operator / double k - returns new Point after divideing x and y by k
* rad(Point a,Point b)- returns the angle of Point a and Point b from this Point
* trunc(double r)     - return Point that if truncated the distance from center to r
* rotleft()           - returns 90 degree ccw rotated point
* rotright()          - returns 90 degree cw rotated point
* rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw
*/
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;
y = _y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%.2f %.2f\n",x,y);
}
bool operator == (Point b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
bool operator < (Point b)const{
return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
//叉积
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
//点积
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
//返回长度
double len(){
return hypot(x,y);//库函数
}
//返回长度的平方
double len2(){
return x*x + y*y;
}
//返回两点的距离
double distance(Point p){
return hypot(x-p.x,y-p.y);
}
Point operator +(const Point &b)const{
return Point(x+b.x,y+b.y);
}
Point operator *(const double &k)const{
return Point(x*k,y*k);
}
Point operator /(const double &k)const{
return Point(x/k,y/k);
}
//计算pa  和  pb 的夹角
//就是求这个点看a,b 所成的夹角
//测试 LightOJ1203
Point p = *this;
return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
}
//化为长度为r的向量
Point trunc(double r){
double l = len();
if(!sgn(l))return *this;
r /= l;
return Point(x*r,y*r);
}
//逆时针旋转90度
Point rotleft(){
return Point(-y,x);
}
//顺时针旋转90度
Point rotright(){
return Point(y,-x);
}
//绕着p点逆时针旋转angle
Point rotate(Point p,double angle){
Point v = (*this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
}
};
/*
* Stores two points
* Line()                         - Empty constructor
* Line(Point _s,Point _e)        - Line through _s and _e
* operator ==                    - checks if two points are same
* Line(Point p,double angle)     - one end p , another end at angle degree
* Line(double a,double b,double c) - Line of equation ax + by + c = 0
* input()                        - inputs s and e
* adjust()                       - orders in such a way that s < e
* length()                       - distance of se
* angle()                        - return 0 <= angle < pi
* relation(Point p)              - 3 if point is on line
*                                  1 if point on the left of line
*                                  2 if point on the right of line
* pointonseg(double p)           - return true if point on segment
* parallel(Line v)               - return true if they are parallel
* segcrossseg(Line v)            - returns 0 if does not intersect
*                                  returns 1 if non-standard intersection
*                                  returns 2 if intersects
* linecrossseg(Line v)           - line and seg
* linecrossline(Line v)          - 0 if parallel
*                                  1 if coincides
*                                  2 if intersects
* crosspoint(Line v)             - returns intersection point
* dispointtoline(Point p)        - distance from point p to the line
* dispointtoseg(Point p)         - distance from p to the segment
* dissegtoseg(Line v)            - distance of two segment
* lineprog(Point p)              - returns projected point p on se line
* symmetrypoint(Point p)         - returns reflection point of p over se
*
*/
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s = _s;
e = _e;
}
bool operator ==(Line v){
return (s == v.s)&&(e == v.e);
}
//根据一个点和倾斜角angle确定直线,0<=angle<pi
Line(Point p,double angle){
s = p;
if(sgn(angle-pi/2) == 0){
e = (s + Point(0,1));
}
else{
e = (s + Point(1,tan(angle)));
}
}
//ax+by+c=0
Line(double a,double b,double c){
if(sgn(a) == 0){
s = Point(0,-c/b);
e = Point(1,-c/b);
}
else if(sgn(b) == 0){
s = Point(-c/a,0);
e = Point(-c/a,1);
}
else{
s = Point(0,-c/b);
e = Point(1,(-c-a)/b);
}
}
void input(){
s.input();
e.input();
}
if(e < s)swap(s,e);
}
//求线段长度
double length(){
return s.distance(e);
}
//返回直线倾斜角 0<=angle<pi
double angle(){
double k = atan2(e.y-s.y,e.x-s.x);
if(sgn(k) < 0)k += pi;
if(sgn(k-pi) == 0)k -= pi;
return k;
}
//点和直线关系
//1  在左侧
//2  在右侧
//3  在直线上
int relation(Point p){
int c = sgn((p-s)^(e-s));
if(c < 0)return 1;
else if(c > 0)return 2;
else return 3;
}
// 点在线段上的判断
bool pointonseg(Point p){
return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
}
//两向量平行(对应直线平行或重合)
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s)) == 0;
}
//两线段相交判断
//2 规范相交
//1 非规范相交
//0 不相交
int segcrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
int d3 = sgn((v.e-v.s)^(s-v.s));
int d4 = sgn((v.e-v.s)^(e-v.s));
if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
}
//直线和线段相交判断
//-*this line   -v seg
//2 规范相交
//1 非规范相交
//0 不相交
int linecrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
//两直线关系
//0 平行
//1 重合
//2 相交
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v){
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
//点到直线的距离
double dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
//点到线段的距离
double dispointtoseg(Point p){
if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
//返回线段到线段的距离
//前提是两线段不相交，相交距离就是0了
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
}
//返回点p在直线上的投影
Point lineprog(Point p){
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//返回点p关于直线的对称点
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};
//圆
struct circle{
Point p;//圆心
double r;//半径
circle(){}
circle(Point _p,double _r){
p = _p;
r = _r;
}
circle(double x,double y,double _r){
p = Point(x,y);
r = _r;
}
//三角形的外接圆
//需要Point的+ /  rotate()  以及Line的crosspoint()
//利用两条边的中垂线得到圆心
//测试：UVA12304
circle(Point a,Point b,Point c){
Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
p = u.crosspoint(v);
r = p.distance(a);
}
//三角形的内切圆
//参数bool t没有作用，只是为了和上面外接圆函数区别
//测试：UVA12304
circle(Point a,Point b,Point c,bool t){
Line u,v;
double m = atan2(b.y-a.y,b.x-a.x), n = atan2(c.y-a.y,c.x-a.x);
u.s = a;
u.e = u.s + Point(cos((n+m)/2),sin((n+m)/2));
v.s = b;
m = atan2(a.y-b.y,a.x-b.x) , n = atan2(c.y-b.y,c.x-b.x);
v.e = v.s + Point(cos((n+m)/2),sin((n+m)/2));
p = u.crosspoint(v);
r = Line(a,b).dispointtoseg(p);
}
//输入
void input(){
p.input();
scanf("%lf",&r);
}
//输出
void output(){
printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);
}
bool operator == (circle v){
return (p==v.p) && sgn(r-v.r)==0;
}
bool operator < (circle v)const{
return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
}
//面积
double area(){
return pi*r*r;
}
//周长
double circumference(){
return 2*pi*r;
}
//点和圆的关系
//0 圆外
//1 圆上
//2 圆内
int relation(Point b){
double dst = b.distance(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r)==0)return 1;
return 0;
}
//线段和圆的关系
//比较的是圆心到线段的距离和半径的关系
int relationseg(Line v){
double dst = v.dispointtoseg(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r) == 0)return 1;
return 0;
}
//直线和圆的关系
//比较的是圆心到直线的距离和半径的关系
int relationline(Line v){
double dst = v.dispointtoline(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r) == 0)return 1;
return 0;
}
//两圆的关系
//5 相离
//4 外切
//3 相交
//2 内切
//1 内含
//需要Point的distance
//测试：UVA12304
int relationcircle(circle v){
double d = p.distance(v.p);
if(sgn(d-r-v.r) > 0)return 5;
if(sgn(d-r-v.r) == 0)return 4;
double l = fabs(r-v.r);
if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;
if(sgn(d-l)==0)return 2;
if(sgn(d-l)<0)return 1;
}
//求两个圆的交点，返回0表示没有交点，返回1是一个交点，2是两个交点
//需要relationcircle
//测试：UVA12304
int pointcrosscircle(circle v,Point &p1,Point &p2){
int rel = relationcircle(v);
if(rel == 1 || rel == 5)return 0;
double d = p.distance(v.p);
double l = (d*d+r*r-v.r*v.r)/(2*d);
double h = sqrt(r*r-l*l);
Point tmp = p + (v.p-p).trunc(l);
p1 = tmp + ((v.p-p).rotleft().trunc(h));
p2 = tmp + ((v.p-p).rotright().trunc(h));
if(rel == 2 || rel == 4)
return 1;
return 2;
}
//求直线和圆的交点，返回交点个数
int pointcrossline(Line v,Point &p1,Point &p2){
if(!(*this).relationline(v))return 0;
Point a = v.lineprog(p);
double d = v.dispointtoline(p);
d = sqrt(r*r-d*d);
if(sgn(d) == 0){
p1 = a;
p2 = a;
return 1;
}
p1 = a + (v.e-v.s).trunc(d);
p2 = a - (v.e-v.s).trunc(d);
return 2;
}
//得到过a,b两点，半径为r1的两个圆
int gercircle(Point a,Point b,double r1,circle &c1,circle &c2){
circle x(a,r1),y(b,r1);
int t = x.pointcrosscircle(y,c1.p,c2.p);
if(!t)return 0;
c1.r = c2.r = r;
return t;
}
//得到与直线u相切，过点q,半径为r1的圆
//测试：UVA12304
int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){
double dis = u.dispointtoline(q);
if(sgn(dis-r1*2)>0)return 0;
if(sgn(dis) == 0){
c1.p = q + ((u.e-u.s).rotleft().trunc(r1));
c2.p = q + ((u.e-u.s).rotright().trunc(r1));
c1.r = c2.r = r1;
return 2;
}
Line u1 = Line((u.s + (u.e-u.s).rotleft().trunc(r1)),(u.e + (u.e-u.s).rotleft().trunc(r1)));
Line u2 = Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e + (u.e-u.s).rotright().trunc(r1)));
circle cc = circle(q,r1);
Point p1,p2;
if(!cc.pointcrossline(u1,p1,p2))cc.pointcrossline(u2,p1,p2);
c1 = circle(p1,r1);
if(p1 == p2){
c2 = c1;
return 1;
}
c2 = circle(p2,r1);
return 2;
}
//同时与直线u,v相切，半径为r1的圆
//测试：UVA12304
int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){
if(u.parallel(v))return 0;//两直线平行
Line u1 = Line(u.s + (u.e-u.s).rotleft().trunc(r1),u.e + (u.e-u.s).rotleft().trunc(r1));
Line u2 = Line(u.s + (u.e-u.s).rotright().trunc(r1),u.e + (u.e-u.s).rotright().trunc(r1));
Line v1 = Line(v.s + (v.e-v.s).rotleft().trunc(r1),v.e + (v.e-v.s).rotleft().trunc(r1));
Line v2 = Line(v.s + (v.e-v.s).rotright().trunc(r1),v.e + (v.e-v.s).rotright().trunc(r1));
c1.r = c2.r = c3.r = c4.r = r1;
c1.p = u1.crosspoint(v1);
c2.p = u1.crosspoint(v2);
c3.p = u2.crosspoint(v1);
c4.p = u2.crosspoint(v2);
return 4;
}
//同时与不相交圆cx,cy相切，半径为r1的圆
//测试：UVA12304
int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){
circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
int t = x.pointcrosscircle(y,c1.p,c2.p);
if(!t)return 0;
c1.r = c2.r = r1;
return t;
}

//过一点作圆的切线(先判断点和圆的关系)
//测试：UVA12304
int tangentline(Point q,Line &u,Line &v){
int x = relation(q);
if(x == 2)return 0;
if(x == 1){
u = Line(q,q + (q-p).rotleft());
v = u;
return 1;
}
double d = p.distance(q);
double l = r*r/d;
double h = sqrt(r*r-l*l);
u = Line(q,p + ((q-p).trunc(l) + (q-p).rotleft().trunc(h)));
v = Line(q,p + ((q-p).trunc(l) + (q-p).rotright().trunc(h)));
return 2;
}
//求两圆相交的面积
double areacircle(circle v){
int rel = relationcircle(v);
if(rel >= 4)return 0.0;
if(rel <= 2)return min(area(),v.area());
double d = p.distance(v.p);
double hf = (r+v.r+d)/2.0;
double ss = 2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
double a1 = acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
a1 = a1*r*r;
double a2 = acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
a2 = a2*v.r*v.r;
return a1+a2-ss;
}
//求圆和三角形pab的相交面积
//测试：POJ3675 HDU3982 HDU2892
double areatriangle(Point a,Point b){
if(sgn((p-a)^(p-b)) == 0)return 0.0;
Point q[5];
int len = 0;
q[len++] = a;
Line l(a,b);
Point p1,p2;
if(pointcrossline(l,q[1],q[2])==2){
if(sgn((a-q[1])*(b-q[1]))<0)q[len++] = q[1];
if(sgn((a-q[2])*(b-q[2]))<0)q[len++] = q[2];
}
q[len++] = b;
if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)swap(q[1],q[2]);
double res = 0;
for(int i = 0;i < len-1;i++){
if(relation(q[i])==0||relation(q[i+1])==0){
res += r*r*arg/2.0;
}
else{
res += fabs((q[i]-p)^(q[i+1]-p))/2.0;
}
}
return res;
}
};

/*
* n,p  Line l for each side
* input(int _n)                        - inputs _n size polygon
* add(Point q)                         - adds a point at end of the list
* getline()                            - populates line array
* cmp                                  - comparision in convex_hull order
* norm()                               - sorting in convex_hull order
* getconvex(polygon &convex)           - returns convex hull in convex
* Graham(polygon &convex)              - returns convex hull in convex
* isconvex()                           - checks if convex
* relationpoint(Point q)               - returns 3 if q is a vertex
*                                                2 if on a side
*                                                1 if inside
*                                                0 if outside
* convexcut(Line u,polygon &po)        - left side of u in po
* gercircumference()                   - returns side length
* getarea()                            - returns area
* getdir()                             - returns 0 for cw, 1 for ccw
* getbarycentre()                      - returns barycenter
*
*/
struct polygon{
int n;
Point p[maxp];
Line l[maxp];
void input(int _n){
n = _n;
for(int i = 0;i < n;i++)
p[i].input();
}
p[n++] = q;
}
void getline(){
for(int i = 0;i < n;i++){
l[i] = Line(p[i],p[(i+1)%n]);
}
}
struct cmp{
Point p;
cmp(const Point &p0){p = p0;}
bool operator()(const Point &aa,const Point &bb){
Point a = aa, b = bb;
int d = sgn((a-p)^(b-p));
if(d == 0){
return sgn(a.distance(p)-b.distance(p)) < 0;
}
return d > 0;
}
};
//进行极角排序
//首先需要找到最左下角的点
//需要重载号好Point的 < 操作符(min函数要用)
void norm(){
Point mi = p[0];
for(int i = 1;i < n;i++)mi = min(mi,p[i]);
sort(p,p+n,cmp(mi));
}
//得到凸包
//得到的凸包里面的点编号是0$\sim$n-1的
//两种凸包的方法
//注意如果有影响，要特判下所有点共点，或者共线的特殊情况
//测试 LightOJ1203  LightOJ1239
void getconvex(polygon &convex){
sort(p,p+n);
convex.n = n;
for(int i = 0;i < min(n,2);i++){
convex.p[i] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
if(n <= 2)return;
int &top = convex.n;
top = 1;
for(int i = 2;i < n;i++){
while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
int temp = top;
convex.p[++top] = p[n-2];
for(int i = n-3;i >= 0;i--){
while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
convex.norm();//原来得到的是顺时针的点，排序后逆时针
}
//得到凸包的另外一种方法
//测试 LightOJ1203  LightOJ1239
void Graham(polygon &convex){
norm();
int &top = convex.n;
top = 0;
if(n == 1){
top = 1;
convex.p[0] = p[0];
return;
}
if(n == 2){
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if(convex.p[0] == convex.p[1])top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for(int i = 2;i < n;i++){
while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )
top--;
convex.p[top++] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
}
//判断是不是凸的
bool isconvex(){
bool s[2];
memset(s,false,sizeof(s));
for(int i = 0;i < n;i++){
int j = (i+1)%n;
int k = (j+1)%n;
s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;
if(s[0] && s[2])return false;
}
return true;
}
//判断点和任意多边形的关系
// 3 点上
// 2 边上
// 1 内部
// 0 外部
int relationpoint(Point q){
for(int i = 0;i < n;i++){
if(p[i] == q)return 3;
}
getline();
for(int i = 0;i < n;i++){
if(l[i].pointonseg(q))return 2;
}
int cnt = 0;
for(int i = 0;i < n;i++){
int j = (i+1)%n;
int k = sgn((q-p[j])^(p[i]-p[j]));
int u = sgn(p[i].y-q.y);
int v = sgn(p[j].y-q.y);
if(k > 0 && u < 0 && v >= 0)cnt++;
if(k < 0 && v < 0 && u >= 0)cnt--;
}
return cnt != 0;
}
//直线u切割凸多边形左侧
//注意直线方向
//测试：HDU3982
void convexcut(Line u,polygon &po){
int &top = po.n;//注意引用
top = 0;
for(int i = 0;i < n;i++){
int d1 = sgn((u.e-u.s)^(p[i]-u.s));
int d2 = sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
if(d1 >= 0)po.p[top++] = p[i];
if(d1*d2 < 0)po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
}
}
//得到周长
//测试 LightOJ1239
double getcircumference(){
double sum = 0;
for(int i = 0;i < n;i++){
sum += p[i].distance(p[(i+1)%n]);
}
return sum;
}
//得到面积
double getarea(){
double sum = 0;
for(int i = 0;i < n;i++){
sum += (p[i]^p[(i+1)%n]);
}
return fabs(sum)/2;
}
//得到方向
// 1 表示逆时针，0表示顺时针
bool getdir(){
double sum = 0;
for(int i = 0;i < n;i++)
sum += (p[i]^p[(i+1)%n]);
if(sgn(sum) > 0)return 1;
return 0;
}
//得到重心
Point getbarycentre(){
Point ret(0,0);
double area = 0;
for(int i = 1;i < n-1;i++){
double tmp = (p[i]-p[0])^(p[i+1]-p[0]);
if(sgn(tmp) == 0)continue;
area += tmp;
ret.x += (p[0].x+p[i].x+p[i+1].x)/3*tmp;
ret.y += (p[0].y+p[i].y+p[i+1].y)/3*tmp;
}
if(sgn(area)) ret = ret/area;
return ret;
}
//多边形和圆交的面积
//测试：POJ3675 HDU3982 HDU2892
double areacircle(circle c){
double ans = 0;
for(int i = 0;i < n;i++){
int j = (i+1)%n;
if(sgn( (p[j]-c.p)^(p[i]-c.p) ) >= 0)
ans += c.areatriangle(p[i],p[j]);
else ans -= c.areatriangle(p[i],p[j]);
}
return fabs(ans);
}
//多边形和圆关系
// 2 圆完全在多边形内
// 1 圆在多边形里面，碰到了多边形边界
// 0 其它
int relationcircle(circle c){
getline();
int x = 2;
if(relationpoint(c.p) != 1)return 0;//圆心不在内部
for(int i = 0;i < n;i++){
if(c.relationseg(l[i])==2)return 0;
if(c.relationseg(l[i])==1)x = 1;
}
return x;
}
};
//AB X AC
double cross(Point A,Point B,Point C){
return (B-A)^(C-A);
}
//AB*AC
double dot(Point A,Point B,Point C){
return (B-A)*(C-A);
}
//最小矩形面积覆盖
// A 必须是凸包(而且是逆时针顺序)
// 测试 UVA 10173
double minRectangleCover(polygon A){
//要特判A.n < 3的情况
if(A.n < 3)return 0.0;
A.p[A.n] = A.p[0];
double ans = -1;
int r = 1, p = 1, q;
for(int i = 0;i < A.n;i++){
//卡出离边A.p[i] - A.p[i+1]最远的点
while( sgn( cross(A.p[i],A.p[i+1],A.p[r+1]) - cross(A.p[i],A.p[i+1],A.p[r]) ) >= 0 )
r = (r+1)%A.n;
//卡出A.p[i] - A.p[i+1]方向上正向n最远的点
while(sgn( dot(A.p[i],A.p[i+1],A.p[p+1]) - dot(A.p[i],A.p[i+1],A.p[p]) ) >= 0 )
p = (p+1)%A.n;
if(i == 0)q = p;
//卡出A.p[i] - A.p[i+1]方向上负向最远的点
while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1]) - dot(A.p[i],A.p[i+1],A.p[q])) <= 0)
q = (q+1)%A.n;
double d = (A.p[i] - A.p[i+1]).len2();
double tmp = cross(A.p[i],A.p[i+1],A.p[r]) *
(dot(A.p[i],A.p[i+1],A.p[p]) - dot(A.p[i],A.p[i+1],A.p[q]))/d;
if(ans < 0 || ans > tmp)ans = tmp;
}
return ans;
}

//直线切凸多边形
//多边形是逆时针的，在q1q2的左侧
//测试:HDU3982
vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2){
vector<Point>qs;
int n = ps.size();
for(int i = 0;i < n;i++){
Point p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = sgn((q2-q1)^(p1-q1)), d2 = sgn((q2-q1)^(p2-q1));
if(d1 >= 0)
qs.push_back(p1);
if(d1 * d2 < 0)
qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
}
return qs;
}
//半平面交
//测试 POJ3335 POJ1474 POJ1279
//***************************
struct halfplane:public Line{
double angle;
halfplane(){}
//表示向量s->e逆时针(左侧)的半平面
halfplane(Point _s,Point _e){
s = _s;
e = _e;
}
halfplane(Line v){
s = v.s;
e = v.e;
}
void calcangle(){
angle = atan2(e.y-s.y,e.x-s.x);
}
bool operator <(const halfplane &b)const{
return angle < b.angle;
}
};
struct halfplanes{
int n;
halfplane hp[maxp];
Point p[maxp];
int que[maxp];
int st,ed;
void push(halfplane tmp){
hp[n++] = tmp;
}
//去重
void unique(){
int m = 1;
for(int i = 1;i < n;i++){
if(sgn(hp[i].angle-hp[i-1].angle) != 0)
hp[m++] = hp[i];
else if(sgn( (hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s) ) > 0)
hp[m-1] = hp[i];
}
n = m;
}
bool halfplaneinsert(){
for(int i = 0;i < n;i++)hp[i].calcangle();
sort(hp,hp+n);
unique();
que[st=0] = 0;
que[ed=1] = 1;
p[1] = hp[0].crosspoint(hp[1]);
for(int i = 2;i < n;i++){
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
que[++ed] = i;
if(hp[i].parallel(hp[que[ed-1]]))return false;
p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
}
while(st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
while(st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
if(st+1>=ed)return false;
return true;
}
//得到最后半平面交得到的凸多边形
//需要先调用halfplaneinsert() 且返回true
void getconvex(polygon &con){
p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
con.n = ed-st+1;
for(int j = st,i = 0;j <= ed;i++,j++)
con.p[i] = p[j];
}
};
//***************************

const int maxn = 1010;
struct circles{
circle c[maxn];
double ans[maxn];//ans[i]表示被覆盖了i次的面积
double pre[maxn];
int n;
circles(){}
c[n++] = cc;
}
//x包含在y中
bool inner(circle x,circle y){
if(x.relationcircle(y) != 1)return 0;
return sgn(x.r-y.r)<=0?1:0;
}
//圆的面积并去掉内含的圆
void init_or(){
bool mark[maxn] = {0};
int i,j,k=0;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++)
if(i != j && !mark[j]){
if( (c[i]==c[j])||inner(c[i],c[j]) )break;
}
if(j < n)mark[i] = 1;
}
for(i = 0;i < n;i++)
if(!mark[i])
c[k++] = c[i];
n = k;
}
//圆的面积交去掉内含的圆
int i,j,k;
bool mark[maxn] = {0};
for(i = 0;i < n;i++){
for(j = 0;j < n;j++)
if(i != j && !mark[j]){
if( (c[i]==c[j])||inner(c[j],c[i]) )break;
}
if(j < n)mark[i] = 1;
}
for(i = 0;i < n;i++)
if(!mark[i])
c[k++] = c[i];
n = k;
}
//半径为r的圆，弧度为th对应的弓形的面积
double areaarc(double th,double r){
return 0.5*r*r*(th-sin(th));
}
//测试SPOJVCIRCLES SPOJCIRUT
//SPOJVCIRCLES求n个圆并的面积，需要加上init\_or()去掉重复圆（否则WA）
//SPOJCIRUT 是求被覆盖k次的面积，不能加init\_or()
//对于求覆盖多少次面积的问题，不能解决相同圆，而且不能init\_or()
//求多圆面积并，需要init\_or,其中一个目的就是去掉相同圆
void getarea(){
memset(ans,0,sizeof(ans));
vector<pair<double,int> >v;
for(int i = 0;i < n;i++){
v.clear();
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
for(int j = 0;j < n;j++)
if(i != j){
Point q = (c[j].p - c[i].p);
double ab = q.len(),ac = c[i].r, bc = c[j].r;
if(sgn(ab+ac-bc)<=0){
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
continue;
}
if(sgn(ab+bc-ac)<=0)continue;
if(sgn(ab-ac-bc)>0)continue;
double th = atan2(q.y,q.x), fai = acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
double a0 = th-fai;
if(sgn(a0+pi)<0)a0+=2*pi;
double a1 = th+fai;
if(sgn(a1-pi)>0)a1-=2*pi;
if(sgn(a0-a1)>0){
v.push_back(make_pair(a0,1));
v.push_back(make_pair(pi,-1));
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(a1,-1));
}
else{
v.push_back(make_pair(a0,1));
v.push_back(make_pair(a1,-1));
}
}
sort(v.begin(),v.end());
int cur = 0;
for(int j = 0;j < v.size();j++){
if(cur && sgn(v[j].first-pre[cur])){
ans[cur] += areaarc(v[j].first-pre[cur],c[i].r);
ans[cur] += 0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
}
cur += v[j].second;
pre[cur] = v[j].first;
}
}
for(int i = 1;i < n;i++)
ans[i] -= ans[i+1];
}
};
三维几何
const double eps = 1e-8;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point3{
double x,y,z;
Point3(double _x = 0,double _y = 0,double _z = 0){
x = _x;
y = _y;
z = _z;
}
void input(){
scanf("%lf%lf%lf",&x,&y,&z);
}
void output(){
scanf("%.2lf %.2lf %.2lf\n",x,y,z);
}
bool operator ==(const Point3 &b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
}
bool operator <(const Point3 &b)const{
return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
}
double len(){
return sqrt(x*x+y*y+z*z);
}
double len2(){
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const{
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
}
Point3 operator -(const Point3 &b)const{
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const{
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const{
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const{
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const{
return x*b.x+y*b.y+z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const{
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
Point3 p = (*this);
return acos( ( (a-p)*(b-p) )/ (a.distance(p)*b.distance(p)) );
}
//变换长度
Point3 trunc(double r){
double l = len();
if(!sgn(l))return *this;
r /= l;
return Point3(x*r,y*r,z*r);
}
};
struct Line3
{
Point3 s,e;
Line3(){}
Line3(Point3 _s,Point3 _e)
{
s = _s;
e = _e;
}
bool operator ==(const Line3 v)
{
return (s==v.s)&&(e==v.e);
}
void input()
{
s.input();
e.input();
}
double length()
{
return s.distance(e);
}
//点到直线距离
double dispointtoline(Point3 p)
{
return ((e-s)^(p-s)).len()/s.distance(e);
}
//点到线段距离
double dispointtoseg(Point3 p)
{
if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
return min(p.distance(s),e.distance(p));
return dispointtoline(p);
}
//返回点p在直线上的投影
Point3 lineprog(Point3 p)
{
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//p绕此向量逆时针arg角度
Point3 rotate(Point3 p,double ang)
{
if(sgn(((s-p)^(e-p)).len()) == 0)return p;
Point3 f1 = (e-s)^(p-s);
Point3 f2 = (e-s)^(f1);
double len = ((s-p)^(e-p)).len()/s.distance(e);
f1 = f1.trunc(len); f2 = f2.trunc(len);
Point3 h = p+f2;
Point3 pp = h+f1;
return h + ((p-h)*cos(ang)) + ((pp-h)*sin(ang));
}
//点在直线上
bool pointonseg(Point3 p)
{
return sgn( ((s-p)^(e-p)).len() ) == 0 && sgn((s-p)*(e-p)) == 0;
}
};
struct Plane
{
Point3 a,b,c,o;//平面上的三个点，以及法向量
Plane(){}
Plane(Point3 _a,Point3 _b,Point3 _c)
{
a = _a;
b = _b;
c = _c;
o = pvec();
}
Point3 pvec()
{
return (b-a)^(c-a);
}
//ax+by+cz+d = 0
Plane(double _a,double _b,double _c,double _d)
{
o = Point3(_a,_b,_c);
if(sgn(_a) != 0)
a = Point3((-_d-_c-_b)/_a,1,1);
else if(sgn(_b) != 0)
a = Point3(1,(-_d-_c-_a)/_b,1);
else if(sgn(_c) != 0)
a = Point3(1,1,(-_d-_a-_b)/_c);
}
//点在平面上的判断
bool pointonplane(Point3 p)
{
return sgn((p-a)*o) == 0;
}
//两平面夹角
double angleplane(Plane f)
{
return acos(o*f.o)/(o.len()*f.o.len());
}
//平面和直线的交点，返回值是交点个数
int crossline(Line3 u,Point3 &p)
{
double x = o*(u.e-a);
double y = o*(u.s-a);
double d = x-y;
if(sgn(d) == 0)return 0;
p = ((u.s*x)-(u.e*y))/d;
return 1;
}
//点到平面最近点(也就是投影)
Point3 pointtoplane(Point3 p)
{
Line3 u = Line3(p,p+o);
crossline(u,p);
return p;
}
//平面和平面的交线
int crossplane(Plane f,Line3 &u)
{
Point3 oo = o^f.o;
Point3 v = o^oo;
double d = fabs(f.o*v);
if(sgn(d) == 0)return 0;
Point3 q = a + (v*(f.o*(f.a-a))/d);
u = Line3(q,q+oo);
return 1;
}
};
平面最近点对
const int MAXN = 100010;
const double eps = 1e-8;
const double INF = 1e20;
struct Point{
double x,y;
void input(){
scanf("%lf%lf",&x,&y);
}
};
double dist(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Point p[MAXN];
Point tmpt[MAXN];
bool cmpx(Point a,Point b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cmpy(Point a,Point b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
double Closest_Pair(int left,int right){
double d = INF;
if(left == right)return d;
if(left+1 == right)return dist(p[left],p[right]);
int mid = (left+right)/2;
double d1 = Closest_Pair(left,mid);
double d2 = Closest_Pair(mid+1,right);
d = min(d1,d2);
int cnt = 0;
for(int i = left;i <= right;i++){
if(fabs(p[mid].x - p[i].x) <= d)
tmpt[cnt++] = p[i];
}
sort(tmpt,tmpt+cnt,cmpy);
for(int i = 0;i < cnt;i++){
for(int j = i+1;j < cnt && tmpt[j].y - tmpt[i].y < d;j++)
d = min(d,dist(tmpt[i],tmpt[j]));
}
return d;
}
int main(){
int n;
while(scanf("%d",&n) == 1 && n){
for(int i = 0;i < n;i++)p[i].input();
sort(p,p+n,cmpx);
printf("%.2lf\n",Closest_Pair(0,n-1));
}
return 0;
}
三维凸包HDU4273
const double eps = 1e-8;
const int MAXN = 550;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point3{
double x,y,z;
Point3(double _x = 0, double _y = 0, double _z = 0){
x = _x;
y = _y;
z = _z;
}
void input(){
scanf("%lf%lf%lf",&x,&y,&z);
}
bool operator ==(const Point3 &b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
}
double len(){
return sqrt(x*x+y*y+z*z);
}
double len2(){
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const{
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
}
Point3 operator -(const Point3 &b)const{
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const{
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const{
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const{
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const{
return x*b.x + y*b.y + z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const{
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
};
struct CH3D{
struct face{
//表示凸包一个面上的三个点的编号
int a,b,c;
//表示该面是否属于最终的凸包上的面
bool ok;
};
//初始顶点数
int n;
Point3 P[MAXN];
//凸包表面的三角形数
int num;
//凸包表面的三角形
face F[8*MAXN];
int g[MAXN][MAXN];
//叉乘
Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c){
return (b-a)^(c-a);
}
//三角形面积*2
double area(Point3 a,Point3 b,Point3 c){
return ((b-a)^(c-a)).len();
}
//四面体有向面积*6
double volume(Point3 a,Point3 b,Point3 c,Point3 d){
return ((b-a)^(c-a))*(d-a);
}
//正：点在面同向
double dblcmp(Point3 &p,face &f){
Point3 p1 = P[f.b] - P[f.a];
Point3 p2 = P[f.c] - P[f.a];
Point3 p3 = p - P[f.a];
return (p1^p2)*p3;
}
void deal(int p,int a,int b){
int f = g[a][b];
if(F[f].ok){
if(dblcmp(P[p],F[f]) > eps)
dfs(p,f);
else {
g[p][b] = g[a][p] = g[b][a] = num;
}
}
}
//递归搜索所有应该从凸包内删除的面
void dfs(int p,int now){
F[now].ok = false;
deal(p,F[now].b,F[now].a);
deal(p,F[now].c,F[now].b);
deal(p,F[now].a,F[now].c);
}
bool same(int s,int t){
Point3 &a = P[F[s].a];
Point3 &b = P[F[s].b];
Point3 &c = P[F[s].c];
return fabs(volume(a,b,c,P[F[t].a])) < eps &&
fabs(volume(a,b,c,P[F[t].b])) < eps &&
fabs(volume(a,b,c,P[F[t].c])) < eps;
}
//构建三维凸包
void create(){
num = 0;

//***********************************
//此段是为了保证前四个点不共面
bool flag = true;
for(int i = 1;i < n;i++){
if(!(P[0] == P[i])){
swap(P[1],P[i]);
flag = false;
break;
}
}
if(flag)return;
flag = true;
for(int i = 2;i < n;i++){
if( ((P[1]-P[0])^(P[i]-P[0])).len() > eps ){
swap(P[2],P[i]);
flag = false;
break;
}
}
if(flag)return;
flag = true;
for(int i = 3;i < n;i++){
if(fabs( ((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]) ) > eps){
swap(P[3],P[i]);
flag = false;
break;
}
}
if(flag)return;
//**********************************

for(int i = 0;i < 4;i++){
}
for(int i = 4;i < n;i++)
for(int j = 0;j < num;j++)
if(F[j].ok && dblcmp(P[i],F[j]) > eps){
dfs(i,j);
break;
}
int tmp = num;
num = 0;
for(int i = 0;i < tmp;i++)
if(F[i].ok)
F[num++] = F[i];
}
//表面积
//测试：HDU3528
double area(){
double res = 0;
if(n == 3){
Point3 p = cross(P[0],P[1],P[2]);
return p.len()/2;
}
for(int i = 0;i < num;i++)
res += area(P[F[i].a],P[F[i].b],P[F[i].c]);
return res/2.0;
}
double volume(){
double res = 0;
Point3 tmp = Point3(0,0,0);
for(int i = 0;i < num;i++)
res += volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
return fabs(res/6);
}
//表面三角形个数
int triangle(){
return num;
}
//表面多边形个数
//测试：HDU3662
int polygon(){
int res = 0;
for(int i = 0;i < num;i++){
bool flag = true;
for(int j = 0;j < i;j++)
if(same(i,j)){
flag = 0;
break;
}
res += flag;
}
return res;
}
//重心
//测试：HDU4273
Point3 barycenter(){
Point3 ans = Point3(0,0,0);
Point3 o = Point3(0,0,0);
double all = 0;
for(int i = 0;i < num;i++){
double vol = volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
ans = ans + (((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
all += vol;
}
ans = ans/all;
return ans;
}
//点到面的距离
//测试：HDU4273
double ptoface(Point3 p,int i){
double tmp1 = fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
double tmp2 = ((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
return tmp1/tmp2;
}
};
CH3D hull;
int main()
{
while(scanf("%d",&hull.n) == 1){
for(int i = 0;i < hull.n;i++)hull.P[i].input();
hull.create();
Point3 p = hull.barycenter();
double ans = 1e20;
for(int i = 0;i < hull.num;i++)
ans = min(ans,hull.ptoface(p,i));
printf("%.3lf\n",ans);
}
return 0;
}

展开全文
• 目录二维几何点线圆 二维几何 点 const double inf=1e20; const double eps=1e-8; const double pi=acos(-1.0); const int maxp=1010; //判断正负 int sgn(double x) { if (fabs(x)<eps) return 0; if (x<0...


目录
二维几何点线圆多边形其他向量运算最小面积覆盖直线切凸多边形半平面交多圆问题平面最近点对

三维几何点线面
三维凸包

二维几何
点
const double inf=1e20;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxp=1010;

//判断正负
int sgn(double x) {
if (fabs(x)<eps) return 0;
if (x<0) return -1;
else return 1;
}
//平方
inline double sqr(double x) {
return x*x;
}

struct Point {
double x,y;
Point() {}
Point(double _x, double _y) {
x=_x;
y=_y;
}
void input() {
scanf("%lf%lf",&x,&y);
}
void output() {
printf("%.2f%.2f\n",x,y);
}
bool operator == (Point b)const {
return sgn(x-b.x)==0 && sgn(y-b.y)==0;
}
bool operator < (Point b)const {
return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
}
Point operator -(const Point &b)const {
return Point(x-b.x,y-b.y);
}
//叉积
double operator ^(const Point &b)const {
return x*b.y-y*b.x;
}
//点积
double operator *(const Point &b)const {
return x*b.x+y*b.y;
}
//返回长度
double len() {
return hypot(x,y);
}
//返回长度平方
double len2() {
return x*x+y*y;
}
//返回两点间距
double distance(Point p) {
return hypot(x-p.x,y-p.y);
}
Point operator +(const Point &b)const {
return Point(x+b.x,y+b.y);
}
Point operator *(const double &k)const {
return Point(x*k,y*k);
}
Point operator /(const double &k)const {
return Point(x/k,y/k);
}
//pa和pb的夹角
Point p=*this;
return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
}
//化为长度为r的向量
Point trunc(double r) {
double l=len();
if (!sgn(l)) return *this;
r/=l;
return Point(x*r,y*r);
}
//逆时针旋转 90 度
Point rotleft() {
return Point(-y,x);
}
//顺时针旋转 90 度
Point rotright() {
return Point(y,-x);
}
//绕着 p 点逆时针旋转 angle
Point rotate(Point p,double angle) {
Point v=(*this)-p;
double c=cos(angle),s=sin(angle);
return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
};

线
struct Line {
Point s,e;
Line() {}
Line(Point _s,Point _e) {
s=_s;
e=_e;
}
bool operator ==(Line v) {
return (s==v.s) && (e==v.e);
}
//根据一个点和倾斜角 angle 确定直线,0<=angle<π
Line(Point p, double angle) {
s=p;
if (sgn(angle-pi/2)==0) {
e=(s+Point(0,1));
}
else {
e=(s+Point(1,tan(angle)));
}
}
//ax+by+c=0
Line(double a,double b,double c) {
if(sgn(a)==0) {
s=Point(0,-c/b);
e=Point(1,-c/b);
}
else if(sgn(b)==0) {
s=Point(-c/a,0);
e=Point(-c/a,1);
}
else {
s=Point(0,-c/b);
e=Point(1,(-c-a)/b);
}
}
void input() {
s.input();
e.input();
}
if(e<s) swap(s,e);
}
//求线段长度
double length() {
return s.distance(e);
}
//返回直线倾斜角 0<=angle<π
double angle() {
double k=atan2(e.y-s.y,e.x-s.x);
if(sgn(k)<0) k+=pi;
if(sgn(k-pi)==0) k-= pi;
return k;
}
//点和直线关系
// 1 在左侧
// 2 在右侧
// 3 在直线上
int relation(Point p) {
int c=sgn((p-s)^(e-s));
if(c<0) return 1;
else if(c>0) return 2;
else return 3;
}
//点在线段上的判断
bool pointonseg(Point p) {
return sgn((p-s)^(e-s))==0 && sgn((p-s)*(p-e))<=0;
}
//两向量平行 (对应直线平行或重合)
bool parallel(Line v) {
return sgn((e-s)^(v.e-v.s))==0;
}
//两线段相交判断
//2 规范相交
//1 非规范相交
//0 不相交
int segcrossseg(Line v) {
int d1=sgn((e-s)^(v.s-s));
int d2=sgn((e-s)^(v.e-s));
int d3=sgn((v.e-v.s)^(s-v.s));
int d4=sgn((v.e-v.s)^(e-v.s));
if((d1^d2)==-2&&(d3^d4)==-2)return 2;
return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
}
//直线和线段相交判断
//-*this line -v seg
//2 规范相交
//1 非规范相交
//0 不相交
int linecrossseg(Line v) {
int d1=sgn((e-s)^(v.s-s));
int d2=sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
//两直线关系
//0 平行
//1 重合
//2 相交
int linecrossline(Line v) {
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v) {
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1
));
}
//点到直线的距离
double dispointtoline(Point p) {
return fabs((p-s)^(e-s))/length();
}
//点到线段的距离
double dispointtoseg(Point p) {
if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
//返回线段到线段的距离
//前提是两线段不相交，相交距离就是 0 了
double dissegtoseg(Line v) {
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v
.dispointtoseg(s),v.dispointtoseg(e)));
}
//返回点 p 在直线上的投影
Point lineprog(Point p) {
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//返回点 p 关于直线的对称点
Point symmetrypoint(Point p) {
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};

圆
struct circle {
Point p; //圆心
double r; //半径
circle() {}
circle(Point _p,double _r) {
p=_p;
r=_r;
}
circle(double x,double y,double _r) {
p=Point(x,y);
r=_r;
}
//三角形的外接圆
//需要 Point 的 + / rotate() 以及 Line 的 crosspoint()
//利用两条边的中垂线得到圆心
circle(Point a,Point b,Point c) {
Line u=Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
Line v=Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
p=u.crosspoint(v);
r=p.distance(a);
}
//三角形的内切圆
//参数 bool t 没有作用，只是为了和上面外接圆函数区别
circle(Point a,Point b,Point c,bool t) {
Line u,v;
double m=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x);
u.s=a;
u.e=u.s+Point(cos((n+m)/2),sin((n+m)/2));
v.s=b;
m=atan2(a.y-b.y,a.x-b.x),n=atan2(c.y-b.y,c.x-b.x);
v.e=v.s+Point(cos((n+m)/2),sin((n+m)/2));
p=u.crosspoint(v);
r=Line(a,b).dispointtoseg(p);
}
void input() {
p.input();
scanf("%lf",&r);
}
void output() {
printf("%.2lf-%.2lf-%.2lf\n",p.x,p.y,r);
}
bool operator == (circle v) {
return (p==v.p) && sgn(r-v.r)==0;
}
bool operator < (circle v)const {
return ((p<v.p) || ((p==v.p) && sgn(r-v.r)<0));
}
//面积
double area() {
return pi*r*r;
}
//周长
double circumference() {
return 2*pi*r;
}
//点和圆的关系
//0 圆外
//1 圆上
//2 圆内
int relation(Point b) {
double dst=b.distance(p);
if (sgn(dst-r)<0) return 2;
else if (sgn(dst-r)==0) return 1;
return 0;
}
//线段和圆的关系
//比较的是圆心到线段的距离和半径的关系
int relationseg(Line v) {
double dst=v.dispointtoseg(p);
if (sgn(dst-r)<0) return 2;
else if (sgn(dst-r)==0) return 1;
return 0;
}
//直线和圆的关系
//比较的是圆心到直线的距离和半径的关系
int relationline(Line v) {
double dst=v.dispointtoline(p);
if (sgn(dst-r)<0) return 2;
else if (sgn(dst-r)==0) return 1;
return 0;
}
//两圆的关系
//5 相离
//4 外切
//3 相交
//2 内切
//1 内含
//需要 Point 的 distance
int relationcircle(circle v) {
double d=p.distance(v.p);
if (sgn(d-r-v.r)>0) return 5;
if (sgn(d-r-v.r)==0) return 4;
double l=fabs(r-v.r);
if (sgn(d-r-v.r)<0 && sgn(d-l)>0) return 3;
if (sgn(d-l)==0) return 2;
if (sgn(d-l)<0) return 1;
}
//求两个圆的交点，返回 0 表示没有交点，返回 1 是一个交点，2 是两个交点
//需要 relationcircle
int pointcrosscircle(circle v,Point &p1,Point &p2) {
int rel=relationcircle(v);
if (rel==1 || rel==5)return 0;
double d=p.distance(v.p);
double l=(d*d+r*r-v.r*v.r)/(2*d);
double h=sqrt(r*r-l*l);
Point tmp=p+(v.p-p).trunc(l);
p1=tmp+((v.p-p).rotleft().trunc(h));
p2=tmp+((v.p-p).rotright().trunc(h));
if(rel==2 || rel==4)
return 1;
return 2;
}
//求直线和圆的交点，返回交点个数
int pointcrossline(Line v,Point &p1,Point &p2) {
if (!(*this).relationline(v)) return 0;
Point a=v.lineprog(p);
double d=v.dispointtoline(p);
d=sqrt(r*r-d*d);
if (sgn(d)==0) {
p1=a;
p2=a;
return 1;
}
p1=a+(v.e-v.s).trunc(d);
p2=a-(v.e-v.s).trunc(d);
return 2;
}
//得到过 a,b 两点，半径为 r1 的两个圆
int gercircle(Point a,Point b,double r1,circle &c1,circle &c2) {
circle x(a,r1),y(b,r1);
int t=x.pointcrosscircle(y,c1.p,c2.p);
if (!t) return 0;
c1.r=c2.r=r;
return t;
}
//得到与直线 u 相切，过点 q, 半径为 r1 的圆
int getcircle(Line u,Point q,double r1,circle &c1,circle &c2) {
double dis = u.dispointtoline(q);
if (sgn(dis-r1*2)>0) return 0;
if (sgn(dis)==0) {
c1.p=q+((u.e-u.s).rotleft().trunc(r1));
c2.p=q+((u.e-u.s).rotright().trunc(r1));
c1.r=c2.r=r1;
return 2;
}

Line u1=Line((u.s+(u.e-u.s).rotleft().trunc(r1)),(u.e+(u.e-u.s).rotleft().trunc(r1)));
Line u2=Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e+(u.e-u.s).rotright().trunc(r1)));
circle cc=circle(q,r1);
Point p1,p2;
if (!cc.pointcrossline(u1,p1,p2))
cc.pointcrossline(u2,p1,p2);
c1=circle(p1,r1);
if (p1==p2) {
c2=c1;
return 1;
}
c2=circle(p2,r1);
return 2;
}
//同时与直线 u,v 相切，半径为 r1 的圆
int getcircle (Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4) {
if(u.parallel(v))return 0;//两直线平行
Line u1=Line(u.s+(u.e-u.s).rotleft().trunc(r1),u.e+(u.e-u.s).rotleft().trunc(r1));
Line u2=Line(u.s+(u.e-u.s).rotright().trunc(r1),u.e+(u.e-u.s).rotright().trunc(r1));
Line v1=Line(v.s+(v.e-v.s).rotleft().trunc(r1),v.e+(v.e-v.s).rotleft().trunc(r1));
Line v2=Line(v.s+(v.e-v.s).rotright().trunc(r1),v.e+(v.e-v.s).rotright().trunc(r1));
c1.r=c2.r=c3.r=c4.r=r1;
c1.p=u1.crosspoint(v1);
c2.p=u1.crosspoint(v2);
c3.p=u2.crosspoint(v1);
c4.p=u2.crosspoint(v2);
return 4;
}
//同时与不相交圆 cx,cy 相切，半径为 r1 的圆
int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2) {
circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
int t=x.pointcrosscircle(y,c1.p,c2.p);
if (!t) return 0;
c1.r=c2.r=r1;
return t;
}

//过一点作圆的切线 (先判断点和圆的关系)
int tangentline(Point q,Line &u,Line &v) {
int x=relation(q);
if (x==2) return 0;
if (x==1) {
u=Line(q,q+(q-p).rotleft());
v=u;
return 1;
}
double d=p.distance(q);
double l=r*r/d;
double h=sqrt(r*r-l*l);
u=Line(q,p+((q-p).trunc(l)+(q-p).rotleft().trunc(h)));
v=Line(q,p+((q-p).trunc(l)+(q-p).rotright().trunc(h)));
return 2;
}
//求两圆相交的面积
double areacircle(circle v) {
int rel=relationcircle(v);
if (rel>=4) return 0.0;
if (rel<=2) return min(area(),v.area());
double d=p.distance(v.p);
double hf=(r+v.r+d)/2.0;
double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
a1=a1*r*r;
double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
a2=a2*v.r*v.r;
return a1+a2-ss;
}
//求圆和三角形 pab 的相交面积
double areatriangle(Point a,Point b) {
if (sgn((p-a)^(p-b))==0) return 0.0;
Point q[5];
int len=0;
q[len++]=a;
Line l(a,b);
Point p1,p2;
if (pointcrossline(l,q[1],q[2])==2) {
if (sgn((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
if (sgn((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
}
q[len++]=b;
if (len==4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
double res=0;
for (int i=0; i<len-1; i++) {
if (relation(q[i])==0||relation(q[i+1])==0) {
res+=r*r*arg/2.0;
}
else {
res+=fabs((q[i]-p)^(q[i+1]-p))/2.0;
}
}
return res;
}
};

多边形
struct polygon {
int n;
Point p[maxp];
Line l[maxp];
void input(int _n) {
n=_n;
for (int i=0; i<n; i++)
p[i].input();
}
p[n++]=q;
}
void getline() {
for(int i=0; i<n; i++) {
l[i]=Line(p[i],p[(i+1)%n]);
}
}
struct cmp {
Point p;
cmp(const Point &p0) {
p=p0;
}
bool operator()(const Point &aa,const Point &bb) {
Point a=aa, b = bb;
int d=sgn((a-p)^(b-p));
if(d==0) {
return sgn(a.distance(p)-b.distance(p))<0;
}
return d>0;
}
};
//进行极角排序
//首先需要找到最左下角的点
//需要重载号好 Point 的 < 操作符 (min 函数要用)
void norm() {
Point mi=p[0];
for (int i=1; i<n; i++)
mi=min(mi,p[i]);
sort(p,p+n,cmp(mi));
}
//得到凸包
//得到的凸包里面的点编号是 0～n-1 的
//两种凸包的方法
//注意如果有影响，要特判下所有点共点，或者共线的特殊情况
void getconvex(polygon &convex) {
sort(p,p+n);
convex.n=n;
for (int i=0; i<min(n,2); i++) {
convex.p[i]=p[i];
}
if (convex.n==2 && (convex.p[0]==convex.p[1]))
convex.n--;//特判
if (n <= 2) return;
int &top=convex.n;
top=1;
for (int i=2; i<n; i++) {
while (top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
top--;
convex.p[++top]=p[i];
}
int temp=top;
convex.p[++top]=p[n-2];
for (int i=n-3; i>=0; i--) {
while (top!=temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
top--;
convex.p[++top]=p[i];
}
if (convex.n==2 && (convex.p[0]==convex.p[1]))
convex.n--;//特判
convex.norm();//原来得到的是顺时针的点，排序后逆时针
}
//得到凸包的另外一种方法
void Graham(polygon &convex) {
norm();
int &top=convex.n;
top=0;
if (n==1) {
top=1;
convex.p[0]=p[0];
return;
}
if (n==2) {
top=2;
convex.p[0]=p[0];
convex.p[1]=p[1];
if(convex.p[0]==convex.p[1]) top--;
return;
}
convex.p[0]=p[0];
convex.p[1]=p[1];
top=2;
for (int i=2; i<n; i++) {
while ( top>1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0)
top--;
convex.p[top++]=p[i];
}
if (convex.n==2 && (convex.p[0]==convex.p[1]))
convex.n--;//特 判
}
//判断是不是凸的
bool isconvex() {
bool s[2];
memset(s,false,sizeof(s));
for (int i=0; i<n; i++) {
int j=(i+1)%n;
int k=(j+1)%n;
s[sgn((p[j]-p[i])^(p[k]-p[i]))+1]=true;
if (s[0] && s[2]) return false;
}
return true;
}
//判断点和任意多边形的关系
// 3 点上
// 2 边上
// 1 内部
// 0 外部
int relationpoint(Point q) {
for (int i=0; i<n; i++) {
if (p[i]==q) return 3;
}
getline();
for (int i=0; i<n; i++) {
if (l[i].pointonseg(q)) return 2;
}
int cnt=0;
for (int i=0; i<n; i++) {
int j=(i+1)%n;
int k=sgn((q-p[j])^(p[i]-p[j]));
int u=sgn(p[i].y-q.y);
int v=sgn(p[j].y-q.y);
if (k>0 && u<0 && v>=0) cnt++;
if (k<0 && v<0 && u>=0) cnt--;
}
return cnt!=0;
}
//直线 u 切割凸多边形左侧
//注意直线方向
void convexcut(Line u,polygon &po) {
int &top=po.n;//注意引用
top=0;
for (int i=0; i<n; i++) {
int d1=sgn((u.e-u.s)^(p[i]-u.s));
int d2=sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
if (d1>=0) po.p[top++]=p[i];
if (d1*d2<0)
po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
}
}
//得到周长
double getcircumference() {
double sum=0;
for (int i=0; i<n; i++) {
sum+=p[i].distance(p[(i+1)%n]);
}
return sum;
}
//得到面积
double getarea() {
double sum=0;
for (int i=0; i<n; i++) {
sum+=(p[i]^p[(i+1)%n]);
}
return fabs(sum)/2;
}
//得到方向
// 1 表示逆时针，0 表示顺时针
bool getdir() {
double sum=0;
for (int i=0; i<n; i++)
sum+=(p[i]^p[(i+1)%n]);
if (sgn(sum)>0) return 1;
return 0;
}
//得到重心
Point getbarycentre() {
Point ret(0,0);
double area=0;
for (int i=1; i<n-1; i++) {
double tmp=(p[i]-p[0])^(p[i+1]-p[0]);
if (sgn(tmp)==0)continue;
area+=tmp;
ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
}
if (sgn(area)) ret=ret/area;
return ret;
}
//多边形和圆交的面积
double areacircle(circle c) {
double ans=0;
for (int i=0; i<n; i++) {
int j=(i+1)%n;
if (sgn((p[j]-c.p)^(p[i]-c.p))>=0)
ans+=c.areatriangle(p[i],p[j]);
else ans-=c.areatriangle(p[i],p[j]);
}
return fabs(ans);
}
//多边形和圆关系
// 2 圆完全在多边形内
// 1 圆在多边形里面，碰到了多边形边界
// 0 其它
int relationcircle(circle c) {
getline();
int x=2;
if (relationpoint(c.p) != 1) return 0;//圆心不在内部
for (int i=0; i<n; i++) {
if (c.relationseg(l[i])==2) return 0;
if (c.relationseg(l[i])==1) x=1;
}
return x;
}
};

其他
向量运算
//AB X AC
double cross(Point A,Point B,Point C) {
return (B-A)^(C-A);
}
//AB*AC
double dot(Point A,Point B,Point C) {
return (B-A)*(C-A);
}

最小面积覆盖
// A 必须是凸包 (而且是逆时针顺序)
double minRectangleCover(polygon A) {
//要特判 A.n < 3 的情况
if (A.n<3) return 0.0;
A.p[A.n]=A.p[0];
double ans=-1;
int r=1,p=1,q;
for(int i=0; i<A.n; i++) {
//卡出离边 A.p[i] - A.p[i+1] 最远的点
while (sgn(cross(A.p[i],A.p[i+1],A.p[r+1])-cross(A.p[i],A.p[i+1],A.p[r]))>=0)
r=(r+1)%A.n;
//卡出 A.p[i] - A.p[i+1] 方向上正向 n 最远的点
while (sgn(dot(A.p[i],A.p[i+1],A.p[p+1])-dot(A.p[i],A.p[i+1],A.p[p]))>=0)
p=(p+1)%A.n;
if (i==0) q=p;
//卡出 A.p[i] - A.p[i+1] 方向上负向最远的点
while (sgn(dot(A.p[i],A.p[i+1],A.p[q+1])-dot(A.p[i],A.p[i+1],A.p[q]))<=0)
q=(q+1)%A.n;
double d=(A.p[i]-A.p[i+1]).len2();
double tmp=cross(A.p[i],A.p[i+1],A.p[r])*(dot(A.p[i],A.p[i+1],A.p[p])-dot(A.p[i],A.p[i+1],A.p[q]))/d;
if (ans<0 || ans>tmp) ans=tmp;
}
return ans;
}

直线切凸多边形
//多边形是逆时针的，在 q1q2 的左侧
vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2) {
vector<Point>qs;
int n=ps.size();
for (int i=0; i<n; i++) {
Point p1=ps[i],p2=ps[(i+1)%n];
int d1=sgn((q2-q1)^(p1-q1)),d2=sgn((q2-q1)^(p2-q1));
if (d1>=0)
qs.push_back(p1);
if (d1*d2<0)
qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
}
return qs;
}

半平面交
struct halfplane:public Line {
double angle;
halfplane() {}
//表示向量 s->e 逆时针 (左侧) 的半平面
halfplane(Point _s,Point _e) {
s=_s;
e=_e;
}
halfplane(Line v) {
s=v.s;
e=v.e;
}
void calcangle() {
angle=atan2(e.y-s.y,e.x-s.x);
}
bool operator <(const halfplane &b)const {
return angle<b.angle;
}
};
struct halfplanes {
int n;
halfplane hp[maxp];
Point p[maxp];
int que[maxp];
int st,ed;
void push(halfplane tmp) {
hp[n++]=tmp;
}
//去重
void unique() {
int m=1;
for (int i=1; i<n; i++) {
if (sgn(hp[i].angle-hp[i-1].angle)!=0)
hp[m++]=hp[i];
else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0)
hp[m-1]=hp[i];
}
n=m;
}
bool halfplaneinsert() {
for (int i=0; i<n; i++) hp[i].calcangle();
sort(hp,hp+n);
unique();
que[st=0]=0;
que[ed=1]=1;
p[1]=hp[0].crosspoint(hp[1]);
for (int i=2; i<n; i++) {
while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)
ed--;
while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)
st++;
que[++ed]=i;
if (hp[i].parallel(hp[que[ed-1]])) return false;
p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
}
while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)
ed--;
while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)
st++;
if (st+1>=ed) return false;
return true;
}
//得到最后半平面交得到的凸多边形
//需要先调用 halfplaneinsert() 且返回 true
void getconvex(polygon &con) {
p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
con.n=ed-st+1;
for(int j=st,i=0; j<=ed; i++,j++)
con.p[i]=p[j];
}
};

多圆问题
const int maxn = 1010;
struct circles {
circle c[maxn];
double ans[maxn];//ans[i] 表示被覆盖了 i 次的面积
double pre[maxn];
int n;
circles() {}
c[n++]=cc;
}
//x 包含在 y 中
bool inner(circle x,circle y) {
if (x.relationcircle(y) != 1) return 0;
return sgn(x.r-y.r)<=0?1:0;
}
//圆的面积并去掉内含的圆
void init_or() {
bool mark[maxn]= {0};
int i,j,k=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++)
if (i!=j && !mark[j]) {
if ((c[i]==c[j]) || inner(c[i],c[j]))
break;
}
if (j<n) mark[i]=1;
}
for (i=0; i<n; i++)
if(!mark[i])
c[k++]=c[i];
n=k;
}
//圆的面积交去掉内含的圆
int i,j,k;
bool mark[maxn] = {0};
for (i=0; i<n; i++) {
for (j=0; j<n; j++)
if (i!=j && !mark[j]) {
if ((c[i]==c[j]) || inner(c[j],c[i])) break;
}
if (j<n) mark[i]=1;
}
for (i=0; i<n; i++)
if (!mark[i])
c[k++]=c[i];
n=k;
}
//半径为 r 的圆，弧度为 th 对应的弓形的面积
double areaarc(double th,double r) {
return 0.5*r*r*(th-sin(th));
}
//测试 SPOJVCIRCLES SPOJCIRUT
//SPOJVCIRCLES 求 n 个圆并的面积，需要加上 init_or() 去掉重复圆（否则WA）
//SPOJCIRUT 是求被覆盖 k 次的面积，不能加 init_or()
//对于求覆盖多少次面积的问题，不能解决相同圆，而且不能 init_or()
//求多圆面积并，需要 init_or, 其中一个目的就是去掉相同圆
void getarea() {
memset(ans,0,sizeof(ans));
vector<pair<double,int> >v;
for(int i=0; i<n; i++) {
v.clear();
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
for (int j=0; j<n; j++)
if (i!=j) {
Point q=(c[j].p-c[i].p);
double ab=q.len(),ac=c[i].r,bc=c[j].r;
if (sgn(ab+ac-bc)<=0) {
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
continue;
}
if (sgn(ab+bc-ac)<=0) continue;
if (sgn(ab-ac-bc)>0) continue;
double th=atan2(q.y,q.x),fai=acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
double a0=th-fai;
if (sgn(a0+pi)<0) a0+=2*pi;
double a1=th+fai;
if (sgn(a1-pi)>0) a1-=2*pi;
if (sgn(a0-a1)>0) {
v.push_back(make_pair(a0,1));
v.push_back(make_pair(pi,-1));
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(a1,-1));
} else {
v.push_back(make_pair(a0,1));
v.push_back(make_pair(a1,-1));
}
}
sort(v.begin(),v.end());
int cur=0;
for (int j=0; j<v.size(); j++) {
if (cur && sgn(v[j].first-pre[cur])) {
ans[cur]+=areaarc(v[j].first-pre[cur],c[i].r);
ans[cur]+=0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))
^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
}
cur+=v[j].second;
pre[cur]=v[j].first;
}
}
for (int i=1; i<n; i++)
ans[i]-=ans[i+1];
}
};

平面最近点对
HDU1007/ZOJ2107
const int MAXN=100010;
const double INF=1e20;
struct Point {
double x,y;
void input() {
scanf("%lf%lf",&x,&y);
}
};
double dist(Point a,Point b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Point p[MAXN];
Point tmpt[MAXN];
bool cmpx(Point a,Point b) {
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
bool cmpy(Point a,Point b) {
return a.y<b.y || (a.y==b.y && a.x<b.x);
}
double Closest_Pair(int left,int right) {
double d=INF;
if (left==right) return d;
if (left+1==right) return dist(p[left],p[right]);
int mid=(left+right)/2;
double d1=Closest_Pair(left,mid);
double d2=Closest_Pair(mid+1,right);
d=min(d1,d2);
int cnt=0;
for (int i=left; i<=right; i++) {
if (fabs(p[mid].x-p[i].x)<=d)
tmpt[cnt++]=p[i];
}
sort(tmpt,tmpt+cnt,cmpy);
for (int i=0; i<cnt; i++) {
for (int j=i+1; j<cnt && tmpt[j].y-tmpt[i].y<d; j++)
d=min(d,dist(tmpt[i],tmpt[j]));
}
return d;
}
int main() {
int n;
while(scanf("%d",&n)==1 && n) {
for(int i=0; i<n; i++) p[i].input();
sort(p,p+n,cmpx);
printf("%.2lf\n",Closest_Pair(0,n-1));
}
return 0;
}


三维几何
点
const double eps=1e-8;
int sgn(double x) {
if (fabs(x)<eps) return 0;
if (x<0) return-1;
else return 1;
}
struct Point3 {
double x,y,z;
Point3(double _x=0,double _y=0,double _z=0) {
x=_x;
y=_y;
z=_z;
}
void input() {
scanf("%lf%lf%lf",&x,&y,&z);
}
void output() {
scanf("%.2lf-%.2lf-%.2lf\n",x,y,z);
}
bool operator ==(const Point3 &b)const {
return sgn(x-b.x)==0 && sgn(y-b.y)==0 && sgn(z-b.z)==0;
}
bool operator <(const Point3 &b)const {
return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
}
double len() {
return sqrt(x*x+y*y+z*z);
}
double len2() {
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const {
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z)
);
}
Point3 operator-(const Point3 &b)const {
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const {
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const {
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const {
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const {
return x*b.x+y*b.y+z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const {
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
Point3 p=(*this);
return acos(((a-p)*(b-p))/(a.distance(p)*b.distance(p)));
}
//变换长度
Point3 trunc(double r) {
double l=len();
if (!sgn(l)) return *this;
r/=l;
return Point3(x*r,y*r,z*r);
}
};

线
struct Line3 {
Point3 s,e;
Line3() {}
Line3(Point3 _s,Point3 _e) {
s=_s;
e=_e;
}
bool operator ==(const Line3 v) {
return (s==v.s)&&(e==v.e);
}
void input() {
s.input();
e.input();
}
double length() {
return s.distance(e);
}
//点到直线距离
double dispointtoline(Point3 p) {
return ((e-s)^(p-s)).len()/s.distance(e);
}
//点到线段距离
double dispointtoseg(Point3 p) {
if (sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s),e.distance(p));
return dispointtoline(p);
}
//返回点 p 在直线上的投影
Point3 lineprog(Point3 p) {
return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
}
//p 绕此向量逆时针 arg 角度
Point3 rotate(Point3 p,double ang) {
if (sgn(((s-p)^(e-p)).len())==0)return p;
Point3 f1=(e-s)^(p-s);
Point3 f2=(e-s)^(f1);
double len=((s-p)^(e-p)).len()/s.distance(e);
f1=f1.trunc(len);
f2=f2.trunc(len);
Point3 h=p+f2;
Point3 pp=h+f1;
return h+((p-h)*cos(ang))+((pp-h)*sin(ang));
}
//点在直线上
bool pointonseg(Point3 p) {
return sgn(((s-p)^(e-p)).len())==0 && sgn((s-p)*(e-p))==0;
}
};

面
struct Plane {
Point3 a,b,c,o;//平面上的三个点，以及法向量
Plane() {}
Plane(Point3 _a,Point3 _b,Point3 _c) {
a=_a;
b=_b;
c=_c;
o=pvec();
}
Point3 pvec() {
return (b-a)^(c-a);
}
//ax+by+cz+d = 0
Plane(double _a,double _b,double _c,double _d) {
o=Point3(_a,_b,_c);
if (sgn(_a)!=0)
a=Point3((-_d-_c-_b)/_a,1,1);
else if (sgn(_b)!=0)
a=Point3(1,(-_d-_c-_a)/_b,1);
else if (sgn(_c)!=0)
a Point3(1,1,(-_d-_a-_b)/_c);
}
//点在平面上的判断
bool pointonplane(Point3 p) {
return sgn((p-a)*o)==0;
}
//两平面夹角
double angleplane(Plane f) {
return acos(o*f.o)/(o.len()*f.o.len());
}
//平面和直线的交点，返回值是交点个数
int crossline(Line3 u,Point3 &p) {
double x=o*(u.e-a);
double y=o*(u.s-a);
double d=x-y;
if (sgn(d)==0) return 0;
p=((u.s*x)-(u.e*y))/d;
return 1;
}
//点到平面最近点 (也就是投影)
Point3 pointtoplane(Point3 p) {
Line3 u=Line3(p,p+o);
crossline(u,p);
return p;
}
//平面和平面的交线
int crossplane(Plane f,Line3 &u) {
Point3 oo=o^f.o;
Point3 v=o^oo;
double d=fabs(f.o*v);
if (sgn(d)==0)return 0;
Point3 q=a+(v*(f.o*(f.a-a))/d);
u=Line3(q,q+oo);
return 1;
}
};

三维凸包
HDU 4273 给一个三维凸包，求重心到表面的最短距离。
const double eps=1e-8;
const int MAXN=550;
int sgn(double x) {
if (fabs(x)<eps) return 0;
if (x<0) return-1;
else return 1;
}
struct Point3 {
double x,y,z;
Point3(double _x=0, double _y=0, double _z=0) {
x=_x;
y=_y;
z=_z;
}
void input() {
scanf("%lf%lf%lf",&x,&y,&z);
}
bool operator ==(const Point3 &b)const {
return sgn(x-b.x)==0 && sgn(y-b.y)==0 && sgn(z-b.z)==0;
}
double len() {
return sqrt(x*x+y*y+z*z);
}
double len2() {
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const {
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
}
Point3 operator-(const Point3 &b)const {
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const {
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const {
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const {
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const {
return x*b.x+y*b.y+z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const {
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
};
struct CH3D {
struct face {
//表示凸包一个面上的三个点的编号
int a,b,c;
//表示该面是否属于最终的凸包上的面
bool ok;
};
//初始顶点数
int n;
Point3 P[MAXN];
//凸包表面的三角形数
int num;
//凸包表面的三角形
face F[8*MAXN];
int g[MAXN][MAXN];
//叉乘
Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c) {
return (b-a)^(c-a);
}
//三角形面积 *2
double area(Point3 a,Point3 b,Point3 c) {
return ((b-a)^(c-a)).len();
}
//四面体有向面积 *6
double volume(Point3 a,Point3 b,Point3 c,Point3 d) {
return ((b-a)^(c-a))*(d-a);
}
//正：点在面同向
double dblcmp(Point3 &p,face &f) {
Point3 p1=P[f.b]-P[f.a];
Point3 p2=P[f.c]-P[f.a];
Point3 p3=p-P[f.a];
return (p1^p2)*p3;
}
void deal(int p,int a,int b) {
int f=g[a][b];
if (F[f].ok) {
if (dblcmp(P[p],F[f])>eps)
dfs(p,f);
else {
g[p][b]=g[a][p]=g[b][a]=num;
}
}
}
//递归搜索所有应该从凸包内删除的面
void dfs(int p,int now) {
F[now].ok=false;
deal(p,F[now].b,F[now].a);
deal(p,F[now].c,F[now].b);
deal(p,F[now].a,F[now].c);
}
bool same(int s,int t) {
Point3 &a=P[F[s].a];
Point3 &b=P[F[s].b];
Point3 &c=P[F[s].c];
return fabs(volume(a,b,c,P[F[t].a]))<eps &&
fabs(volume(a,b,c,P[F[t].b]))<eps &&
fabs(volume(a,b,c,P[F[t].c]))<eps;
}
//构建三维凸包
void create() {
num=0;
//***********************************
//此段是为了保证前四个点不共面
bool flag=true;
for (int i=1; i<n; i++) {
if (!(P[0]==P[i])) {
swap(P[1],P[i]);
flag=false;
break;
}
}
if (flag)return;
flag=true;
for (int i=2; i<n; i++) {
if(((P[1]-P[0])^(P[i]-P[0])).len()>eps) {
swap(P[2],P[i]);
flag=false;
break;
}
}
if (flag) return;
flag=true;
for (int i=3; i<n; i++) {
if (fabs(((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]))>eps) {
swap(P[3],P[i]);
flag=false;
break;
}
}
if (flag) return;
//**********************************

for (int i=0; i<4; i++) {
}
for (int i=4; i<n; i++)
for (int j=0; j<num; j++)
if (F[j].ok && dblcmp(P[i],F[j])>eps) {
dfs(i,j);
break;
}
int tmp=num;
num=0;
for (int i=0; i<tmp; i++)
if (F[i].ok)
F[num++]=F[i];
}
//表面积
double area() {
double res=0;
if (n==3) {
Point3 p=cross(P[0],P[1],P[2]);
return p.len()/2;
}
for (int i=0; i<num; i++)
res+=area(P[F[i].a],P[F[i].b],P[F[i].c]);
return res/2.0;
}
//体积
double volume() {
double res=0;
Point3 tmp=Point3(0,0,0);
for (int i=0; i<num; i++)
res+=volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
return fabs(res/6);
}
//表面三角形个数
int triangle() {
return num;
}
//表面多边形个数
int polygon() {
int res=0;
for (int i=0; i<num; i++) {
bool flag=true;
for (int j=0; j<i; j++)
if (same(i,j)) {
flag=0;
break;
}
res+=flag;
}
return res;
}
//重心
Point3 barycenter() {
Point3 ans=Point3(0,0,0);
Point3 o=Point3(0,0,0);
double all=0;
for (int i=0; i<num; i++) {
double vol=volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
ans=ans+(((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
all+=vol;
}
ans=ans/all;
return ans;
}
//点到面的距离
double ptoface(Point3 p,int i) {
double tmp1=fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
double tmp2=((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
return tmp1/tmp2;
}
};
CH3D hull;
int main() {
while(scanf("%d",&hull.n)==1) {
for(int i=0; i<hull.n; i++) hull.P[i].input();
hull.create();
Point3 p=hull.barycenter();
double ans=1e20;
for(int i=0; i<hull.num; i++)
ans=min(ans,hull.ptoface(p,i));
printf("%.3lf\n",ans);
}
return 0;
}

展开全文
• 计算几何我觉得一靠板子，二靠细节。我会在另一篇博客整理出比较好的板子。细节得要自己培养培养，总不能总看网上的数据来过题呀。 C - Segments 题目大意：给出n条线段两个端点的坐标，问所有线段投影到一条直线...
感觉做完没什么进步，不会做的题就去搜题解，没过的题就去找数据。。。下次不能这样！  计算几何我觉得一靠板子，二靠细节。我会在另一篇博客整理出比较好的板子。细节得要自己培养培养，总不能总看网上的数据来过题呀。  C - Segments  题目大意：给出n条线段两个端点的坐标，问所有线段投影到一条直线上，如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。  解题思路：如果有存在这样的直线，过投影相交区域作直线的垂线，该垂线必定与每条线段相交，问题转化为问是否存在一条线和所有线段相交.  直线肯定经过两个端点。  枚举端点，判断直线和线段是否相交。  细节要注意，判断重合点。  还有就是加入只有一条线段的话，刚好直线是过同一条直线的。  所以保险的做法是枚举所有的两个端点，包括同一条直线的。(kuangbin的题解)  枚举端点是个常见的思路，往往端点就是极端情况。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<set>
using namespace std;
const double eps = 1e-8;
struct point
{
int index;
double ang;
double x, y;
point() { x = 0;y = 0; }
point(double sx, double sy) { x = sx, y = sy; }
bool operator<(const point &b)const
{
if (x != b.x)return x < b.x;
return y < b.y;
}

};
struct line
{
double ang;
point a, b;line(){}
line(const point &p1, const point &p2)
{
a = p1;
b = p2;
}
};

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int opposite_side(point p1, point p2,line l)
{
double tmp = xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b);
return  tmp < -eps || tmp < eps;
}
set<point>S;
line lines[105];
int n;
bool check(line a)
{
for (int i = 1;i <= n;i++)
{
point tmp1 = lines[i].a;
point tmp2 = lines[i].b;
if (!opposite_side(tmp1, tmp2, a))
return 0;
}
return 1;
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
S.clear();

scanf("%d", &n);
double x1, y1, x2, y2;
for (int i = 1;i <= n;i++)
{
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
S.insert(point(x1, y1));
S.insert(point(x2, y2));
lines[i] = line(point(x1, y1), point(x2, y2));
}
set<point>::iterator itor,itor2;
bool flag = false;
for(itor=S.begin();itor!=S.end();itor++)
for (itor2 = itor;itor2 != S.end();itor2++)
{
if (itor2 == itor)continue;
line tmp = line(*itor, *itor2);
if (check(tmp))
{
flag = true;
puts("Yes!");
itor = S.end();
itor--;
break;
}
}
if (!flag)
puts("No!");
}

}

E - The Doors  这题应该能做出来的，当时蠢了一下。。先计算出端点到其他能到的点的距离，然后跑最短路就行了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;

#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
#define zero(x) (fabs(x)<eps)

struct point
{
int index;
double x, y;
point() { x = 0, y = 0; }
point(double sx, double sy)
{
x = sx;
y = sy;
}
};

struct line
{
point a, b;
line() {}
line(const point &p1, const point &p2)
{
a = p1;
b = p2;
}
};
vector<line>V;

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int opposite_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}

int intersect_ex(line u, line v)
{
return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}

int parallel(line u, line v)
{
return zero((u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y));
}

double dist(line a)
{
double x = a.a.x - a.b.x;
double y = a.a.y - a.b.y;
return sqrt(x*x + y*y);
}

point P[100];
int pcnt;
double map[100][100];
void buildmap()
{
for(int i=1;i<=pcnt;i++)
for (int j = i + 1;j <= pcnt;j++)
{
map[i][j] = map[j][i] = 50.0;
line tmp = line(P[i], P[j]);
bool flag = true;
for (int k = 0;k < V.size();k++)
{
line tmp2 = V[k];
if (parallel(tmp, tmp2))continue;
if (intersect_ex(tmp, tmp2))
{
flag = false;
break;
}
}
if (flag)
map[i][j] = map[j][i] = dist(tmp);
}
}
bool vis[100];
double d[100];

struct HeapNode
{
int u;
double d;
HeapNode(int _u,double _d):u(_u),d(_d){}
HeapNode(){}
bool operator<(const HeapNode &b)const
{
return d > b.d;
}
};

double dijkstra()
{
memset(vis, 0, sizeof(vis));
for (int i = 1;i <= pcnt;i++)d[i] = 50;
d[1] = 0;
priority_queue<HeapNode>Q;
Q.push(HeapNode(1,d[1]));
while (!Q.empty())
{
HeapNode x = Q.top();Q.pop();
if (vis[x.u])continue;
vis[x.u] = 1;
for (int i = 1;i <= pcnt;i++)if(map[x.u][i]!=50)
{
if (d[i] > d[x.u] + map[x.u][i])
{
d[i] = d[x.u] + map[x.u][i];
Q.push(HeapNode(i, d[i]));
}
}
}
return d[2];
}

int main()
{
int n;
while (~scanf("%d", &n) && n != -1)
{
pcnt = 0;
V.clear();
double tmp1, tmp2, tmp3;
//line tmp;
P[++pcnt] = point(0, 5);
P[++pcnt] = point(10, 5);
for (int i = 1;i <= n;i++)
{
scanf("%lf %lf", &tmp1, &tmp2);
//P[++pcnt] = point(tmp1, 0);
P[++pcnt] = point(tmp1, tmp2);
V.push_back(line(point(tmp1, 0), point(tmp1, tmp2)));
scanf("%lf %lf", &tmp2, &tmp3);
P[++pcnt] = point(tmp1, tmp2);
P[++pcnt] = point(tmp1, tmp3);
V.push_back(line(point(tmp1, tmp2), point(tmp1, tmp3)));
scanf("%lf", &tmp2);
P[++pcnt] = point(tmp1, tmp2);
V.push_back(line(point(tmp1, tmp2), point(tmp1, 10)));
}
buildmap();
printf("%.2f\n", dijkstra());
}

}

G - Treasure Hunt  这题一开始我的思路想着把它转换成最短路，不同的房间如果隔着一个墙就连条边，然后和最外面的再连一条边，这样就可以求最短路了。但想了很久不知道怎么划分房间。。  正解还是枚举端点，端点和终点相连的线段看与多少个墙相交(不包括端点)。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring>
using namespace std;
#define eps 1e-5
struct point
{
double x, y;
point() { x = 0, y = 0; }
point(double sx, double sy)
{
x = sx;
y = sy;
}
}P[100];
int now;
struct line
{
point a, b;
line(){}
line(point p1, point p2)
{
a = p1;
b = p2;
}
}lines[35];
double aimx, aimy;
int n;

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int opposite_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}

int intersect_ex(line u, line v)
{
return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}

void solve()
{
if (n == 0) { printf("Number of doors = 1\n");return; }
int ans = 35;
point aim = point(aimx, aimy);
for (int i = 1;i <= now;i++)
{
line tmp = line(P[i], aim);
int ctch = 0;
for (int j = 1;j <= n;j++)
{
if (intersect_ex(tmp, lines[j]))
ctch++;
}
ans = min(ans, ctch);
}
printf("Number of doors = %d\n", ans+1);
}

int main()
{

scanf("%d", &n);
int x1, y1, x2, y2;
now = 0;
for (int i = 1;i <= n;i++)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
P[++now] = point(x1, y1);
P[++now] = point(x2, y2);
lines[i] = line(P[now - 1], P[now]);
}
scanf("%lf %lf", &aimx, &aimy);
solve();
}
H - Intersection  本专题傻题之一。题目挺简单的，但这题有几个坑点。  1，给出的矩形的两个点并不一定是按照顺序给出的，需要自己判断。  2，线段在矩形内部也算相交(无语)。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<math.h>
using namespace std;
#define eps 1e-5
#define zero(x) (fabs(x)<eps)
struct point
{
int x, y;
point() { x = 0, y = 0; }
point(int sx, int sy) { x = sx;y = sy; }
};
int xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

struct line
{
point a, b;
line() {}
line(point _a, point _b) :a(_a), b(_b) {}
};

int dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}

int same_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}

int dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}

int intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int x1, y1, x2, y2;
int x3, y3, x4, y4;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
line a = line(point(x1, y1), point(x2, y2));
scanf("%d %d %d %d", &x3, &y3, &x4, &y4);
if (x3 > x4)swap(x3, x4);
if (y3 < y4)swap(y3, y4);
point a1 = point(x3, y3), a2 = point(x4, y3), a3 = point(x3, y4), a4 = point(x4, y4);
line l1 = line(a1, a2), l2 = line(a1, a3), l3 = line(a3, a4), l4 = line(a2, a4);
if (!intersect_in(a, l1) && !intersect_in(a, l2) && !intersect_in(a, l3) && !intersect_in(a, l4))
{
point tmp = a.a;
if (tmp.x<x4&&tmp.x>x3&&tmp.y<y3&&tmp.y>y4)
puts("T");
else
puts("F");

}
else
puts("T");
}
}

I - Space Ant   一开始的思路没错，但是样例都没过，就发现我对极角排序有一点错误的理解。叉积极角排序只能排不超过π范围的点，如果超过了就得先按照象限排，再叉积极角排序。  另外atan2那种排序方式范围是-π到π，换句话说就是从第三象限排(如果我没搞错的话)。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<math.h>
using namespace std;

#define eps 1e-5
#define zero(x) (fabs(x)<eps)

struct point
{
int index;
int x, y;
point(){}
point(int _x,int _y,int idx):x(_x),y(_y),index(idx){}
};

int xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

double dist(point a, point b)
{
double x = a.x - b.x;
double y = a.y - b.y;
return sqrt(x*x + y*y);
}

struct line
{
point a, b;
double ang;
line(point sa, point sb)
{
a = sa;
b = sb;
}
line(){}
bool operator<(const line &y)const
{
if (zero(ang - y.ang))
{
return dist(a, b) < dist(y.a, y.b);
}
return ang < y.ang;
}
void getang()
{
ang = atan2(-b.y + a.y, -b.x + a.x);
}
};
point P[105];
int N;
int ans[105];
int cnt;
point now;
bool cmp(const point &a, const point &b)
{
int tmp = xmult(a, b, now);
if (tmp == 0)
return dist(a, now) < dist(b, now);
return tmp > 0;
}
void solve(int themin)
{
cnt = 0;

now = point(0, themin,0);
for (int i = 1;i <= N;i++)
{
sort(P + i, P + N + 1,cmp);
ans[++cnt] = P[i].index;
now = P[i];
}
printf("%d", N);
for (int i = 1;i <= N;i++)
printf(" %d", ans[i]);
puts("");
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{

scanf("%d", &N);
int idx, x, y;
int miny = 105;
for (int i = 1;i <= N;i++)
{
scanf("%d %d %d", &idx, &x, &y);
P[idx] = point(x, y,idx);
miny = min(miny, y);
}
solve(miny);
}
}


2–√

2

$\sqrt2$，那么它的x坐标就变成整数了。  如何求一个正方形的位置呢，我们可以枚举它之前放好的正方形，先假设它靠在这个正方形上，求出当前的x，然后找到一个最大的x就是他的位置啦。  求完位置后在看它左边的正方形把它遮住了多少，右边的正方形把它遮住了多少，在判断一下就行了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<vector>
using namespace std;

int B[55], L[55];
vector<int>V;
int main()
{
int n;
while (~scanf("%d",&n)&&n)
{
V.clear();
int tmp;
for (int i = 1;i <= n;i++)
{
scanf("%d", &tmp);
int x = tmp;
L[i] = tmp;
for (int j = 1;j < i;j++)
{
if (tmp >= L[j])
x = max(x, B[j] + L[j] + L[j]);
else
x = max(x, B[j] + tmp * 2);
}
B[i] = x;
}

int ans = 0;
for (int i = 1;i <= n;i++)
{
int Left=0, Right=B[i]+L[i];
for (int j = 1;j < i;j++)
{
int x = B[j] + L[j];
if (x >= B[i] - L[i])
Left = max(Left, x);
}
for (int j = i + 1;j <= n;j++)
{
int x = B[j] - L[j];
if (x <= B[i] + L[i])
Right = min(Right, x);
}
if (Left < Right)V.push_back(i);
}
for (int i = 0;i < V.size();i++)
{
printf("%d", V[i]);
if (i != V.size() - 1)printf(" ");
else
puts("");
}
//printf("%d\n", ans);
}
}

K - An Easy Problem?!
一道坑题，但不得不说它是道好题。需要判断的地方很多，希望读者自行判断。。  提一点最重要的地方，就是有可能上面的板子遮住了下面的板子，使得一点雨都就不住。  注意精度问题，用C++交。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<stdio.h>
using namespace std;
#define eps 1e-8
#define zero(x) (fabs(x)<eps)
struct point
{
double x, y;
point(double sx, double sy) { x = sx;y = sy; }
point(){}
};

struct line
{
point a, b;
double ang;
line(){}
line(point p1, point p2)
{
a = p1;b = p2;
}
void getang()
{
ang = atan2((b.y - a.y) , (b.x - a.x));
}
};

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int same_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}

int dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}

int dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}

int intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}

point intersection(line u, line v)
{
point ret = u.a;
double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x)) / ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));
ret.x += (u.b.x - u.a.x)*t;
ret.y += (u.b.y - u.a.y)*t;
return ret;
}

double area_triangle(point p1, point p2, point p3)
{
return fabs(xmult(p1, p2, p3)) / 2;
}

int parallel(line u, line v)
{
return zero((u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y));
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
double x1, y1, x2, y2, x3, y3, x4, y4;
scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
point p1 = point(x1, y1), p2 = point(x2, y2), p3 = point(x3, y3), p4 = point(x4, y4);
if (p1.y < p2.y)
swap(p1, p2);
if (p3.y < p4.y)
swap(p3, p4);
if (p1.y > p3.y)
{
swap(p1, p3);
swap(p2, p4);
}
line a = line(p1, p2);
line b = line(p3, p4);
a.getang();b.getang();
if (p1.x < p2.x&&p3.x<p4.x)
{
if (a.ang > b.ang&&p3.x<=p1.x)
{
puts("0.00");
continue;
}
}
if (p1.x > p2.x&&p3.x > p4.x)
{
if (a.ang < b.ang&&p3.x>=p1.x)
{
puts("0.00");
continue;
}
}

if (intersect_in(a, b))
{

if (zero(a.ang - b.ang))puts("0.00");
else
{
point insec1 = intersection(a, b);
line c = line(p1, point(p1.x+5, p1.y));
if (parallel(c, b))
puts("0.00");
else
{
point insec2 = intersection(c, b);
printf("%.2f\n", area_triangle(insec1, insec2, p1));
}
}

}
else
puts("0.00");
}

}

L - Pipe   此题初看可能十分困难，但是上下顶点对于限制光线非常关键。首先，我们想到如果一根光线自始至终未曾擦到任何顶点，肯定不是最优的(可以通过平移使之优化)。然后，如果只碰到一个顶点，那也不是最优的，可以通过旋转使他碰到另一个顶点，并且更优，最后要说明，最优光线必然是擦到一个上顶点和一个下顶点。以上三步的证明用反证法并不困难。所以留给读者。  于是有了一个简单的算法，任取一个上顶点和下顶点，形成直线l。若l能射穿左入口，即当x=x0时，直线l在(x0,y0)和(x0,y0-1)之间，则是一条可行光线。再从左到右依次判断每条上，下管壁是否与l相交，相交则求交点，并把交点x与当前最佳值比较，若所有管壁都不与l相交，说明l射穿了整个管道。(算法艺术与信息学竞赛)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<stdio.h>
using namespace std;
#define eps 1e-5
#define zero(x) (fabs(x)<eps)
#define inf 1e10

int sgn(double x)
{
if (fabs(x) < eps)return 0;
if (x < 0)return -1;
return 1;
}

struct point
{
double x, y;
point(double sx, double sy)
{
x = sx;
y = sy;
}
point(){}
}up[50],dwn[50];
struct line
{
point a, b;
line(point sa, point sb)
{
a = sa;
b = sb;
}
line(){}
}L[50];

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int opposite_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}

int intersect_ex(line u, line v)
{
return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
}

int same_side(point p1, point p2, line l)
{
double tmp= xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b);
cout << tmp << endl;
cout << (tmp > eps) << endl;
return tmp > eps;
}

int dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}

int dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}

int intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}

int n;

double dist(point a, point b)
{
double x = a.x - b.x;
double y = a.y - b.y;
return sqrt(x*x + y*y);
}

point intersection(line u, line v)
{
point ret = u.a;
double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x)) / ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));
ret.x += (u.b.x - u.a.x)*t;
ret.y += (u.b.y - u.a.y)*t;
return ret;
}

int Seg_inter_line(line l1, line l2)//判断直线l1和线段l2是否相交
{
double tmp1 = xmult(l2.a, l1.a, l1.b);
double tmp2 = xmult(l2.b, l1.a, l1.b);
return sgn(tmp1)*sgn(tmp2) <= 0;
}

void solve()
{
line first = line(up[1], dwn[1]);
double ans = -inf;
for(int i=1;i<=n;i++)
for (int j = 1;j <= n;j++)
{
line it = line(up[i], dwn[j]);
if (Seg_inter_line(it,first))
{
for (int k = 1;k <= n;k++)
{
line now = line(up[k], dwn[k]);
if (!Seg_inter_line(it, now))
{
line tmp1 = line(up[k], up[k - 1]);
line tmp2 = line(dwn[k], dwn[k - 1]);
if (Seg_inter_line(it, tmp1))
{
point t = intersection(it, tmp1);
ans = max(ans, t.x);
}
if (Seg_inter_line(it, tmp2))
{
point t = intersection(it, tmp2);
ans = max(ans, t.x);
}
break;
}
if (k == n)
{
ans = up[n].x + 1;
}
}

}
}
if (zero(ans - up[n].x-1))
puts("Through all the pipe.");
else
printf("%.2f\n", ans);

}

int main()
{
while (~scanf("%d",&n)&&n)
{
double x, y;
for (int i = 1;i <= n;i++)
{
scanf("%lf %lf", &x, &y);
up[i] = point(x, y);
dwn[i] = point(x, y - 1);
}
solve();
}
}
M - Geometric Shapes  本专题最傻的题。本来不想贴的，但感觉代码写的太好了，所以贴上来。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
#define eps 1e-5
#define zero(x) (fabs(x)<eps)
const double pi = acos(-1);
struct point
{
double x, y;
point(double sa, double sb)
{
x = sa;
y = sb;
}
point() {}
bool operator<(const point &b)const
{
if (x != b.x)
return x < b.x;
return y < b.y;
}
};

struct line
{
char s;
point a, b;
line(point sa, point sb, char ss)
{
a = sa;
b = sb;
s = ss;
}
line() {}
};
line L[1000];
int lcnt;

point rotate(point v, point p, double angle)
{
point ret = p;
v.x -= p.x, v.y -= p.y;
p.x = cos(angle);
p.y = sin(angle);
ret.x += v.x*p.x - v.y*p.y;
ret.y += v.x*p.y + v.y*p.x;
return ret;
}

{
char tmp1[50], tmp2[50];
scanf("%s %s", tmp1, tmp2);
int x1, y1, x2, y2;
sscanf(tmp1, "(%d,%d)", &x1, &y1);
sscanf(tmp2, "(%d,%d)", &x2, &y2);
point p1 = point(x1, y1);
point p2 = point(x2, y2);
point p3, p4;
point mid = point((x1 + x2 + 0.0) / 2.0, (y1 + y2 + 0.0) / 2.0);
p3 = rotate(p1, mid, pi / 2);
p4 = rotate(p1, mid, -pi / 2);

L[++lcnt] = line(p1, p3, s);
L[++lcnt] = line(p1, p4, s);
L[++lcnt] = line(p2, p3, s);
L[++lcnt] = line(p2, p4, s);
}

{
char tmp1[50], tmp2[50], tmp3[50];
scanf("%s %s %s", tmp1, tmp2, tmp3);
int x1, y1, x2, y2, x3, y3;
sscanf(tmp1, "(%d,%d)", &x1, &y1);
sscanf(tmp2, "(%d,%d)", &x2, &y2);
sscanf(tmp3, "(%d,%d)", &x3, &y3);
point p[4];
p[0] = point(x1, y1);
p[1] = point(x2, y2);
p[2] = point(x3, y3);

p[3] = point(p[2].x + (p[0].x - p[1].x), p[2].y - (p[1].y - p[0].y));
L[++lcnt] = line(p[0], p[1], s);
L[++lcnt] = line(p[1], p[2], s);
L[++lcnt] = line(p[2], p[3], s);
L[++lcnt] = line(p[0], p[3], s);
}

{
char tmp1[50], tmp2[50];
scanf("%s %s", tmp1, tmp2);
int x1, y1, x2, y2;
sscanf(tmp1, "(%d,%d)", &x1, &y1);
sscanf(tmp2, "(%d,%d)", &x2, &y2);
point a = point(x1, y1);
point b = point(x2, y2);
L[++lcnt] = line(a, b,s);
}

{
char tmp1[50], tmp2[50], tmp3[50];
scanf("%s %s %s", tmp1, tmp2, tmp3);
int x1, y1, x2, y2, x3, y3;
sscanf(tmp1, "(%d,%d)", &x1, &y1);
sscanf(tmp2, "(%d,%d)", &x2, &y2);
sscanf(tmp3, "(%d,%d)", &x3, &y3);
point a = point(x1, y1);
point b = point(x2, y2);
point c = point(x3, y3);
L[++lcnt] = line(a, b,s);
L[++lcnt] = line(a, c,s);
L[++lcnt] = line(b, c,s);
}

{
int num;
scanf("%d", &num);
int x1, y1;
char tmp1[50];
scanf("%s", tmp1);
sscanf(tmp1, "(%d,%d)", &x1, &y1);
int beforex = x1, beforey = y1;
int nowx, nowy;
for (int i = 2;i <= num;i++)
{
scanf("%s", tmp1);
sscanf(tmp1, "(%d,%d)", &nowx, &nowy);
L[++lcnt] = line(point(beforex, beforey), point(nowx, nowy),s);
beforex = nowx;
beforey = nowy;
}
L[++lcnt] = line(point(x1, y1), point(nowx, nowy), s);
}
bool col[30][30];
bool have[30];
{
if (change)
{
lcnt = 0;
memset(col, 0, sizeof(col));
memset(have, 0, sizeof(have));
}

char str[5];
scanf("%s", str);
if (str[0] == s)return 0;
have[str[0] - 'A'] = 1;
string type;
cin >> type;
if (type[0] == 's')
else if (type[0] == 'r')
else if (type[0] == 'l')
else if (type[0] == 't')
else if (type[0] == 'p')
return 1;
}

double xmult(point p1, point p2, point p0)
{
return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

int dots_inline(point p1, point p2, point p3)
{
return zero(xmult(p1, p2, p3));
}

int same_side(point p1, point p2, line l)
{
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}

int dot_online_in(point p, line l)
{
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
}

int intersect_in(line u, line v)
{
if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
}

int check(int num,int &flag)
{
int cnt = 0;
for (int i = 0;i < 26;i++)if (col[num][i])cnt++;
if (cnt == 1)
flag = 1;
else if (cnt == 2)
flag = 2;
else flag = 3;
for (int i = 25;i >= 0;i--)if (col[num][i])
return i;
return -1;
}

void solve()
{
for(int i=1;i<=lcnt;i++)
for (int j = i + 1;j <= lcnt;j++)if(L[i].s!=L[j].s)
{
if (intersect_in(L[i], L[j]))
{
col[L[i].s-'A'][L[j].s-'A'] = col[L[j].s-'A'][L[i].s-'A'] = 1;
}
}
for (int i = 0;i < 26;i++)if (have[i])
{
printf("%c", 'A' + i);
int flag;
int last = check(i,flag);
if (last==-1)
puts(" has no intersections");
else
{
printf(" intersects with");
if (flag == 1)
{
printf(" %c\n", last + 'A');
}
else if (flag == 2)
{
for (int j = 0;j <= last;j++)
{
if (!col[i][j])
continue;
char tmp = j + 'A';
if (j != last)
printf(" %c", tmp);
else
printf(" and %c\n", tmp);
}
}
else
{
for (int j = 0;j <= last;j++)
{
if (!col[i][j])
continue;
char tmp = j + 'A';
if (j != last)
printf(" %c,", tmp);
else
printf(" and %c\n", tmp);
}
}
}
}

}

int main()
{
string name;
{
solve();
puts("");
}

}

N - A Round Peg in a Ground Hole   一道模板题。先用叉积判断是不是凸包，再判断圆心是否在多边形内部，再用距离判断多边形是否把圆包围。
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int MAXN = 1e3 + 7;
const double EPS = 1e-8;
const double oo = 1e10 + 7;

struct Point
{
double x, y;
Point(double x = 0, double y = 0) :x(x), y(y) {}
Point operator - (const Point &tmp)const {
return Point(x - tmp.x, y - tmp.y);
}
double operator ^(const Point &tmp)const {
return x*tmp.y - y*tmp.x;
}
double operator *(const Point &tmp)const {
return x*tmp.x + y*tmp.y;
}
};
double Dist(Point a, Point b)
{///两点间的距离
return sqrt((a - b)*(a - b));
}
int Sign(double t)
{
if (t > EPS)return 1;
if (fabs(t) < EPS)return 0;
return -1;///负数
}
struct Segment
{
Point S, E;
Segment(Point S = 0, Point E = 0) :S(S), E(E) {}
bool OnSeg(const Point &p)
{///点是否在线段上
if (Sign((S - E) ^ (p - E)) == 0)///共线
if (Sign((p.x - S.x)*(p.x - E.x)) <= 0)///位于线段的中间或者端点
if (Sign((p.y - S.y)*(p.y - E.y)) <= 0)
return true;
return false;
}
bool Inter(const Segment &tmp)
{///只考虑完全相交的情况
return Sign((S - E) ^ (tmp.S - E)) * Sign((S - E) ^ (tmp.E - E)) == -1;
}
Point NearPoint(const Point &p)
{///点到线段最近的点
Point res;
double r = ((E - S)*(p - S)) / ((E - S)*(E - S));

if (r > EPS && (1.0 - r) > EPS)
{///点在线段的投影在线段上
res.x = S.x + r * (E.x - S.x);
res.y = S.y + r * (E.y - S.y);
}
else
{///求离最近的端点
if (Dist(p, S) < Dist(p, E))
res = S;
else
res = E;
}

return res;
}
};
struct Poly
{
int N;
Point vertex[MAXN];

bool IsConvex()
{///判断是否是凸多边形，可以共线
int vis[3] = { 0 };
for (int i = 0; i<N; i++)
{///如果同时出现整数和负数，说明存在凹的
int k = Sign((vertex[(i + 1) % N] - vertex[i]) ^ (vertex[(i + 2) % N] - vertex[i]));
vis[k + 1] = 1;

if (vis[0] && vis[2])
return false;
}
return true;
}
int InPoly(const Point &Q)
{///判断点Q是否在多边形内，射线法，奇数在内，偶数在外
///在圆上返回0， 圆外-1， 圆内 1
Segment ray(Point(-oo, Q.y), Q);///构造射线的最远处
int cnt = 0;///统计相交的边数

for (int i = 0; i<N; i++)
{
Segment edge(vertex[i], vertex[(i + 1) % N]);

if (edge.OnSeg(Q) == true)
return 0;///点在边上

if (ray.OnSeg(vertex[i]) == true)
{///如果相交连接点，那么取y值小的点
if (vertex[(i + 1) % N].y - vertex[i].y > EPS)
cnt++;
}
else if (ray.OnSeg(vertex[(i + 1) % N]) == true)
{
if (vertex[i].y - vertex[(i + 1) % N].y > EPS)
cnt++;
}
else if (ray.Inter(edge) && edge.Inter(ray))
cnt++;
}

if (cnt % 2)
return 1;
else
return -1;
}
};
struct Circle
{
Point center;///圆心
double R;///半径
};

bool Find(Poly &a, Circle &c)
{///判断圆是否在多边形内
if (a.InPoly(c.center) == -1)
return false;///如果圆心在多边形外面

for (int i = 0; i<a.N; i++)
{
Segment edge(a.vertex[i], a.vertex[(i + 1) % a.N]);
double len = Dist(c.center, edge.NearPoint(c.center));

if (Sign(len - c.R) < 0)
return false;
}

return true;
}

int main()
{
Poly a;///定义多边形
Circle c;///定义圆

while (scanf("%d", &a.N) != EOF && a.N > 2)
{
scanf("%lf%lf%lf", &c.R, &c.center.x, &c.center.y);
for (int i = 0; i<a.N; i++)
scanf("%lf%lf", &a.vertex[i].x, &a.vertex[i].y);

if (a.IsConvex() == false)
printf("HOLE IS ILL-FORMED\n");
else if (Find(a, c) == false)
printf("PEG WILL NOT FIT\n");
else
printf("PEG WILL FIT\n");
}

return 0;
}

之后会把整理的模板贴上来。
展开全文
• // 计算几何模板 const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const int maxp = 1010; //Compares a double to zero int sgn(double x){ if(fabs(x) <...

二维几何部分

// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}
/*
* Point
* Point()               - Empty constructor
* Point(double _x,double _y)  - constructor
* input()             - double input
* output()            - %.2f output
* operator ==         - compares x and y
* operator <          - compares first by x, then by y
* operator -          - return new Point after subtracting curresponging x and y
* operator ^          - cross product of 2d points
* operator *          - dot product
* len()               - gives length from origin
* len2()              - gives square of length from origin
* distance(Point p)   - gives distance from p
* operator + Point b  - returns new Point after adding curresponging x and y
* operator * double k - returns new Point after multiplieing x and y by k
* operator / double k - returns new Point after divideing x and y by k
* rad(Point a,Point b)- returns the angle of Point a and Point b from this Point
* trunc(double r)     - return Point that if truncated the distance from center to r
* rotleft()           - returns 90 degree ccw rotated point
* rotright()          - returns 90 degree cw rotated point
* rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw
*/
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;
y = _y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%.2f %.2f\n",x,y);
}
bool operator == (Point b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
bool operator < (Point b)const{
return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
//叉积
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
//点积
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
//返回长度
double len(){
return hypot(x,y);//库函数
}
//返回长度的平方
double len2(){
return x*x + y*y;
}
//返回两点的距离
double distance(Point p){
return hypot(x-p.x,y-p.y);
}
Point operator +(const Point &b)const{
return Point(x+b.x,y+b.y);
}
Point operator *(const double &k)const{
return Point(x*k,y*k);
}
Point operator /(const double &k)const{
return Point(x/k,y/k);
}
//计算pa  和  pb 的夹角
//就是求这个点看a,b 所成的夹角
//测试 LightOJ1203
Point p = *this;
return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
}
//化为长度为r的向量
Point trunc(double r){
double l = len();
if(!sgn(l))return *this;
r /= l;
return Point(x*r,y*r);
}
//逆时针旋转90度
Point rotleft(){
return Point(-y,x);
}
//顺时针旋转90度
Point rotright(){
return Point(y,-x);
}
//绕着p点逆时针旋转angle
Point rotate(Point p,double angle){
Point v = (*this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
}
};
/*
* Stores two points
* Line()                         - Empty constructor
* Line(Point _s,Point _e)        - Line through _s and _e
* operator ==                    - checks if two points are same
* Line(Point p,double angle)     - one end p , another end at angle degree
* Line(double a,double b,double c) - Line of equation ax + by + c = 0
* input()                        - inputs s and e
* adjust()                       - orders in such a way that s < e
* length()                       - distance of se
* angle()                        - return 0 <= angle < pi
* relation(Point p)              - 3 if point is on line
*                                  1 if point on the left of line
*                                  2 if point on the right of line
* pointonseg(double p)           - return true if point on segment
* parallel(Line v)               - return true if they are parallel
* segcrossseg(Line v)            - returns 0 if does not intersect
*                                  returns 1 if non-standard intersection
*                                  returns 2 if intersects
* linecrossseg(Line v)           - line and seg
* linecrossline(Line v)          - 0 if parallel
*                                  1 if coincides
*                                  2 if intersects
* crosspoint(Line v)             - returns intersection point
* dispointtoline(Point p)        - distance from point p to the line
* dispointtoseg(Point p)         - distance from p to the segment
* dissegtoseg(Line v)            - distance of two segment
* lineprog(Point p)              - returns projected point p on se line
* symmetrypoint(Point p)         - returns reflection point of p over se
*
*/
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s = _s;
e = _e;
}
bool operator ==(Line v){
return (s == v.s)&&(e == v.e);
}
//根据一个点和倾斜角angle确定直线,0<=angle<pi
Line(Point p,double angle){
s = p;
if(sgn(angle-pi/2) == 0){
e = (s + Point(0,1));
}
else{
e = (s + Point(1,tan(angle)));
}
}
//ax+by+c=0
Line(double a,double b,double c){
if(sgn(a) == 0){
s = Point(0,-c/b);
e = Point(1,-c/b);
}
else if(sgn(b) == 0){
s = Point(-c/a,0);
e = Point(-c/a,1);
}
else{
s = Point(0,-c/b);
e = Point(1,(-c-a)/b);
}
}
void input(){
s.input();
e.input();
}
if(e < s)swap(s,e);
}
//求线段长度
double length(){
return s.distance(e);
}
//返回直线倾斜角 0<=angle<pi
double angle(){
double k = atan2(e.y-s.y,e.x-s.x);
if(sgn(k) < 0)k += pi;
if(sgn(k-pi) == 0)k -= pi;
return k;
}
//点和直线关系
//1  在左侧
//2  在右侧
//3  在直线上
int relation(Point p){
int c = sgn((p-s)^(e-s));
if(c < 0)return 1;
else if(c > 0)return 2;
else return 3;
}
// 点在线段上的判断
bool pointonseg(Point p){
return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
}
//两向量平行(对应直线平行或重合)
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s)) == 0;
}
//两线段相交判断
//2 规范相交
//1 非规范相交
//0 不相交
int segcrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
int d3 = sgn((v.e-v.s)^(s-v.s));
int d4 = sgn((v.e-v.s)^(e-v.s));
if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
}
//直线和线段相交判断
//-*this line   -v seg
//2 规范相交
//1 非规范相交
//0 不相交
int linecrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
//两直线关系
//0 平行
//1 重合
//2 相交
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v){
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
//点到直线的距离
double dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
//点到线段的距离
double dispointtoseg(Point p){
if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
//返回线段到线段的距离
//前提是两线段不相交，相交距离就是0了
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
}
//返回点p在直线上的投影
Point lineprog(Point p){
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//返回点p关于直线的对称点
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};
//圆
struct circle{
Point p;//圆心
double r;//半径
circle(){}
circle(Point _p,double _r){
p = _p;
r = _r;
}
circle(double x,double y,double _r){
p = Point(x,y);
r = _r;
}
//三角形的外接圆
//需要Point的+ /  rotate()  以及Line的crosspoint()
//利用两条边的中垂线得到圆心
//测试：UVA12304
circle(Point a,Point b,Point c){
Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
p = u.crosspoint(v);
r = p.distance(a);
}
//三角形的内切圆
//参数bool t没有作用，只是为了和上面外接圆函数区别
//测试：UVA12304
circle(Point a,Point b,Point c,bool t){
Line u,v;
double m = atan2(b.y-a.y,b.x-a.x), n = atan2(c.y-a.y,c.x-a.x);
u.s = a;
u.e = u.s + Point(cos((n+m)/2),sin((n+m)/2));
v.s = b;
m = atan2(a.y-b.y,a.x-b.x) , n = atan2(c.y-b.y,c.x-b.x);
v.e = v.s + Point(cos((n+m)/2),sin((n+m)/2));
p = u.crosspoint(v);
r = Line(a,b).dispointtoseg(p);
}
//输入
void input(){
p.input();
scanf("%lf",&r);
}
//输出
void output(){
printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);
}
bool operator == (circle v){
return (p==v.p) && sgn(r-v.r)==0;
}
bool operator < (circle v)const{
return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
}
//面积
double area(){
return pi*r*r;
}
//周长
double circumference(){
return 2*pi*r;
}
//点和圆的关系
//0 圆外
//1 圆上
//2 圆内
int relation(Point b){
double dst = b.distance(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r)==0)return 1;
return 0;
}
//线段和圆的关系
//比较的是圆心到线段的距离和半径的关系
int relationseg(Line v){
double dst = v.dispointtoseg(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r) == 0)return 1;
return 0;
}
//直线和圆的关系
//比较的是圆心到直线的距离和半径的关系
int relationline(Line v){
double dst = v.dispointtoline(p);
if(sgn(dst-r) < 0)return 2;
else if(sgn(dst-r) == 0)return 1;
return 0;
}
//两圆的关系
//5 相离
//4 外切
//3 相交
//2 内切
//1 内含
//需要Point的distance
//测试：UVA12304
int relationcircle(circle v){
double d = p.distance(v.p);
if(sgn(d-r-v.r) > 0)return 5;
if(sgn(d-r-v.r) == 0)return 4;
double l = fabs(r-v.r);
if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;
if(sgn(d-l)==0)return 2;
if(sgn(d-l)<0)return 1;
}
//求两个圆的交点，返回0表示没有交点，返回1是一个交点，2是两个交点
//需要relationcircle
//测试：UVA12304
int pointcrosscircle(circle v,Point &p1,Point &p2){
int rel = relationcircle(v);
if(rel == 1 || rel == 5)return 0;
double d = p.distance(v.p);
double l = (d*d+r*r-v.r*v.r)/(2*d);
double h = sqrt(r*r-l*l);
Point tmp = p + (v.p-p).trunc(l);
p1 = tmp + ((v.p-p).rotleft().trunc(h));
p2 = tmp + ((v.p-p).rotright().trunc(h));
if(rel == 2 || rel == 4)
return 1;
return 2;
}
//求直线和圆的交点，返回交点个数
int pointcrossline(Line v,Point &p1,Point &p2){
if(!(*this).relationline(v))return 0;
Point a = v.lineprog(p);
double d = v.dispointtoline(p);
d = sqrt(r*r-d*d);
if(sgn(d) == 0){
p1 = a;
p2 = a;
return 1;
}
p1 = a + (v.e-v.s).trunc(d);
p2 = a - (v.e-v.s).trunc(d);
return 2;
}
//得到过a,b两点，半径为r1的两个圆
int gercircle(Point a,Point b,double r1,circle &c1,circle &c2){
circle x(a,r1),y(b,r1);
int t = x.pointcrosscircle(y,c1.p,c2.p);
if(!t)return 0;
c1.r = c2.r = r;
return t;
}
//得到与直线u相切，过点q,半径为r1的圆
//测试：UVA12304
int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){
double dis = u.dispointtoline(q);
if(sgn(dis-r1*2)>0)return 0;
if(sgn(dis) == 0){
c1.p = q + ((u.e-u.s).rotleft().trunc(r1));
c2.p = q + ((u.e-u.s).rotright().trunc(r1));
c1.r = c2.r = r1;
return 2;
}
Line u1 = Line((u.s + (u.e-u.s).rotleft().trunc(r1)),(u.e + (u.e-u.s).rotleft().trunc(r1)));
Line u2 = Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e + (u.e-u.s).rotright().trunc(r1)));
circle cc = circle(q,r1);
Point p1,p2;
if(!cc.pointcrossline(u1,p1,p2))cc.pointcrossline(u2,p1,p2);
c1 = circle(p1,r1);
if(p1 == p2){
c2 = c1;
return 1;
}
c2 = circle(p2,r1);
return 2;
}
//同时与直线u,v相切，半径为r1的圆
//测试：UVA12304
int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){
if(u.parallel(v))return 0;//两直线平行
Line u1 = Line(u.s + (u.e-u.s).rotleft().trunc(r1),u.e + (u.e-u.s).rotleft().trunc(r1));
Line u2 = Line(u.s + (u.e-u.s).rotright().trunc(r1),u.e + (u.e-u.s).rotright().trunc(r1));
Line v1 = Line(v.s + (v.e-v.s).rotleft().trunc(r1),v.e + (v.e-v.s).rotleft().trunc(r1));
Line v2 = Line(v.s + (v.e-v.s).rotright().trunc(r1),v.e + (v.e-v.s).rotright().trunc(r1));
c1.r = c2.r = c3.r = c4.r = r1;
c1.p = u1.crosspoint(v1);
c2.p = u1.crosspoint(v2);
c3.p = u2.crosspoint(v1);
c4.p = u2.crosspoint(v2);
return 4;
}
//同时与不相交圆cx,cy相切，半径为r1的圆
//测试：UVA12304
int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){
circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
int t = x.pointcrosscircle(y,c1.p,c2.p);
if(!t)return 0;
c1.r = c2.r = r1;
return t;
}

//过一点作圆的切线(先判断点和圆的关系)
//测试：UVA12304
int tangentline(Point q,Line &u,Line &v){
int x = relation(q);
if(x == 2)return 0;
if(x == 1){
u = Line(q,q + (q-p).rotleft());
v = u;
return 1;
}
double d = p.distance(q);
double l = r*r/d;
double h = sqrt(r*r-l*l);
u = Line(q,p + ((q-p).trunc(l) + (q-p).rotleft().trunc(h)));
v = Line(q,p + ((q-p).trunc(l) + (q-p).rotright().trunc(h)));
return 2;
}
//求两圆相交的面积
double areacircle(circle v){
int rel = relationcircle(v);
if(rel >= 4)return 0.0;
if(rel <= 2)return min(area(),v.area());
double d = p.distance(v.p);
double hf = (r+v.r+d)/2.0;
double ss = 2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
double a1 = acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
a1 = a1*r*r;
double a2 = acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
a2 = a2*v.r*v.r;
return a1+a2-ss;
}
//求圆和三角形pab的相交面积
//测试：POJ3675 HDU3982 HDU2892
double areatriangle(Point a,Point b){
if(sgn((p-a)^(p-b)) == 0)return 0.0;
Point q[5];
int len = 0;
q[len++] = a;
Line l(a,b);
Point p1,p2;
if(pointcrossline(l,q[1],q[2])==2){
if(sgn((a-q[1])*(b-q[1]))<0)q[len++] = q[1];
if(sgn((a-q[2])*(b-q[2]))<0)q[len++] = q[2];
}
q[len++] = b;
if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)swap(q[1],q[2]);
double res = 0;
for(int i = 0;i < len-1;i++){
if(relation(q[i])==0||relation(q[i+1])==0){
res += r*r*arg/2.0;
}
else{
res += fabs((q[i]-p)^(q[i+1]-p))/2.0;
}
}
return res;
}
};

/*
* n,p  Line l for each side
* input(int _n)                        - inputs _n size polygon
* add(Point q)                         - adds a point at end of the list
* getline()                            - populates line array
* cmp                                  - comparision in convex_hull order
* norm()                               - sorting in convex_hull order
* getconvex(polygon &convex)           - returns convex hull in convex
* Graham(polygon &convex)              - returns convex hull in convex
* isconvex()                           - checks if convex
* relationpoint(Point q)               - returns 3 if q is a vertex
*                                                2 if on a side
*                                                1 if inside
*                                                0 if outside
* convexcut(Line u,polygon &po)        - left side of u in po
* gercircumference()                   - returns side length
* getarea()                            - returns area
* getdir()                             - returns 0 for cw, 1 for ccw
* getbarycentre()                      - returns barycenter
*
*/
struct polygon{
int n;
Point p[maxp];
Line l[maxp];
void input(int _n){
n = _n;
for(int i = 0;i < n;i++)
p[i].input();
}
p[n++] = q;
}
void getline(){
for(int i = 0;i < n;i++){
l[i] = Line(p[i],p[(i+1)%n]);
}
}
struct cmp{
Point p;
cmp(const Point &p0){p = p0;}
bool operator()(const Point &aa,const Point &bb){
Point a = aa, b = bb;
int d = sgn((a-p)^(b-p));
if(d == 0){
return sgn(a.distance(p)-b.distance(p)) < 0;
}
return d > 0;
}
};
//进行极角排序
//首先需要找到最左下角的点
//需要重载号好Point的 < 操作符(min函数要用) 
void norm(){
Point mi = p[0];
for(int i = 1;i < n;i++)mi = min(mi,p[i]);
sort(p,p+n,cmp(mi));
}
//得到凸包
//得到的凸包里面的点编号是0$\sim$n-1的
//两种凸包的方法
//注意如果有影响，要特判下所有点共点，或者共线的特殊情况
//测试 LightOJ1203  LightOJ1239
void getconvex(polygon &convex){
sort(p,p+n);
convex.n = n;
for(int i = 0;i < min(n,2);i++){
convex.p[i] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
if(n <= 2)return;
int &top = convex.n;
top = 1;
for(int i = 2;i < n;i++){
while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
int temp = top;
convex.p[++top] = p[n-2];
for(int i = n-3;i >= 0;i--){
while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
convex.norm();//原来得到的是顺时针的点，排序后逆时针
}
//得到凸包的另外一种方法
//测试 LightOJ1203  LightOJ1239
void Graham(polygon &convex){
norm();
int &top = convex.n;
top = 0;
if(n == 1){
top = 1;
convex.p[0] = p[0];
return;
}
if(n == 2){
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if(convex.p[0] == convex.p[1])top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for(int i = 2;i < n;i++){
while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )
top--;
convex.p[top++] = p[i];
}
if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
}
//判断是不是凸的
bool isconvex(){
bool s[2];
memset(s,false,sizeof(s));
for(int i = 0;i < n;i++){
int j = (i+1)%n;
int k = (j+1)%n;
s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;
if(s[0] && s[2])return false;
}
return true;
}
//判断点和任意多边形的关系
// 3 点上
// 2 边上
// 1 内部
// 0 外部
int relationpoint(Point q){
for(int i = 0;i < n;i++){
if(p[i] == q)return 3;
}
getline();
for(int i = 0;i < n;i++){
if(l[i].pointonseg(q))return 2;
}
int cnt = 0;
for(int i = 0;i < n;i++){
int j = (i+1)%n;
int k = sgn((q-p[j])^(p[i]-p[j]));
int u = sgn(p[i].y-q.y);
int v = sgn(p[j].y-q.y);
if(k > 0 && u < 0 && v >= 0)cnt++;
if(k < 0 && v < 0 && u >= 0)cnt--;
}
return cnt != 0;
}
//直线u切割凸多边形左侧
//注意直线方向
//测试：HDU3982
void convexcut(Line u,polygon &po){
int &top = po.n;//注意引用
top = 0;
for(int i = 0;i < n;i++){
int d1 = sgn((u.e-u.s)^(p[i]-u.s));
int d2 = sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
if(d1 >= 0)po.p[top++] = p[i];
if(d1*d2 < 0)po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
}
}
//得到周长
//测试 LightOJ1239
double getcircumference(){
double sum = 0;
for(int i = 0;i < n;i++){
sum += p[i].distance(p[(i+1)%n]);
}
return sum;
}
//得到面积
double getarea(){
double sum = 0;
for(int i = 0;i < n;i++){
sum += (p[i]^p[(i+1)%n]);
}
return fabs(sum)/2;
}
//得到方向
// 1 表示逆时针，0表示顺时针
bool getdir(){
double sum = 0;
for(int i = 0;i < n;i++)
sum += (p[i]^p[(i+1)%n]);
if(sgn(sum) > 0)return 1;
return 0;
}
//得到重心
Point getbarycentre(){
Point ret(0,0);
double area = 0;
for(int i = 1;i < n-1;i++){
double tmp = (p[i]-p[0])^(p[i+1]-p[0]);
if(sgn(tmp) == 0)continue;
area += tmp;
ret.x += (p[0].x+p[i].x+p[i+1].x)/3*tmp;
ret.y += (p[0].y+p[i].y+p[i+1].y)/3*tmp;
}
if(sgn(area)) ret = ret/area;
return ret;
}
//多边形和圆交的面积
//测试：POJ3675 HDU3982 HDU2892
double areacircle(circle c){
double ans = 0;
for(int i = 0;i < n;i++){
int j = (i+1)%n;
if(sgn( (p[j]-c.p)^(p[i]-c.p) ) >= 0)
ans += c.areatriangle(p[i],p[j]);
else ans -= c.areatriangle(p[i],p[j]);
}
return fabs(ans);
}
//多边形和圆关系
// 2 圆完全在多边形内
// 1 圆在多边形里面，碰到了多边形边界
// 0 其它
int relationcircle(circle c){
getline();
int x = 2;
if(relationpoint(c.p) != 1)return 0;//圆心不在内部
for(int i = 0;i < n;i++){
if(c.relationseg(l[i])==2)return 0;
if(c.relationseg(l[i])==1)x = 1;
}
return x;
}
};
//AB X AC
double cross(Point A,Point B,Point C){
return (B-A)^(C-A);
}
//AB*AC
double dot(Point A,Point B,Point C){
return (B-A)*(C-A);
}
//最小矩形面积覆盖
// A 必须是凸包(而且是逆时针顺序)
// 测试 UVA 10173
double minRectangleCover(polygon A){
//要特判A.n < 3的情况
if(A.n < 3)return 0.0;
A.p[A.n] = A.p[0];
double ans = -1;
int r = 1, p = 1, q;
for(int i = 0;i < A.n;i++){
//卡出离边A.p[i] - A.p[i+1]最远的点
while( sgn( cross(A.p[i],A.p[i+1],A.p[r+1]) - cross(A.p[i],A.p[i+1],A.p[r]) ) >= 0 )
r = (r+1)%A.n;
//卡出A.p[i] - A.p[i+1]方向上正向n最远的点
while(sgn( dot(A.p[i],A.p[i+1],A.p[p+1]) - dot(A.p[i],A.p[i+1],A.p[p]) ) >= 0 )
p = (p+1)%A.n;
if(i == 0)q = p;
//卡出A.p[i] - A.p[i+1]方向上负向最远的点
while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1]) - dot(A.p[i],A.p[i+1],A.p[q])) <= 0)
q = (q+1)%A.n;
double d = (A.p[i] - A.p[i+1]).len2();
double tmp = cross(A.p[i],A.p[i+1],A.p[r]) *
(dot(A.p[i],A.p[i+1],A.p[p]) - dot(A.p[i],A.p[i+1],A.p[q]))/d;
if(ans < 0 || ans > tmp)ans = tmp;
}
return ans;
}

//直线切凸多边形
//多边形是逆时针的，在q1q2的左侧
//测试:HDU3982
vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2){
vector<Point>qs;
int n = ps.size();
for(int i = 0;i < n;i++){
Point p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = sgn((q2-q1)^(p1-q1)), d2 = sgn((q2-q1)^(p2-q1));
if(d1 >= 0)
qs.push_back(p1);
if(d1 * d2 < 0)
qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
}
return qs;
}
//半平面交
//测试 POJ3335 POJ1474 POJ1279
//***************************
struct halfplane:public Line{
double angle;
halfplane(){}
//表示向量s->e逆时针(左侧)的半平面
halfplane(Point _s,Point _e){
s = _s;
e = _e;
}
halfplane(Line v){
s = v.s;
e = v.e;
}
void calcangle(){
angle = atan2(e.y-s.y,e.x-s.x);
}
bool operator <(const halfplane &b)const{
return angle < b.angle;
}
};
struct halfplanes{
int n;
halfplane hp[maxp];
Point p[maxp];
int que[maxp];
int st,ed;
void push(halfplane tmp){
hp[n++] = tmp;
}
//去重
void unique(){
int m = 1;
for(int i = 1;i < n;i++){
if(sgn(hp[i].angle-hp[i-1].angle) != 0)
hp[m++] = hp[i];
else if(sgn( (hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s) ) > 0)
hp[m-1] = hp[i];
}
n = m;
}
bool halfplaneinsert(){
for(int i = 0;i < n;i++)hp[i].calcangle();
sort(hp,hp+n);
unique();
que[st=0] = 0;
que[ed=1] = 1;
p[1] = hp[0].crosspoint(hp[1]);
for(int i = 2;i < n;i++){
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
while(st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
que[++ed] = i;
if(hp[i].parallel(hp[que[ed-1]]))return false;
p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
}
while(st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
while(st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
if(st+1>=ed)return false;
return true;
}
//得到最后半平面交得到的凸多边形
//需要先调用halfplaneinsert() 且返回true
void getconvex(polygon &con){
p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
con.n = ed-st+1;
for(int j = st,i = 0;j <= ed;i++,j++)
con.p[i] = p[j];
}
};
//***************************

const int maxn = 1010;
struct circles{
circle c[maxn];
double ans[maxn];//ans[i]表示被覆盖了i次的面积
double pre[maxn];
int n;
circles(){}
c[n++] = cc;
}
//x包含在y中
bool inner(circle x,circle y){
if(x.relationcircle(y) != 1)return 0;
return sgn(x.r-y.r)<=0?1:0;
}
//圆的面积并去掉内含的圆
void init_or(){
bool mark[maxn] = {0};
int i,j,k=0;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++)
if(i != j && !mark[j]){
if( (c[i]==c[j])||inner(c[i],c[j]) )break;
}
if(j < n)mark[i] = 1;
}
for(i = 0;i < n;i++)
if(!mark[i])
c[k++] = c[i];
n = k;
}
//圆的面积交去掉内含的圆
int i,j,k;
bool mark[maxn] = {0};
for(i = 0;i < n;i++){
for(j = 0;j < n;j++)
if(i != j && !mark[j]){
if( (c[i]==c[j])||inner(c[j],c[i]) )break;
}
if(j < n)mark[i] = 1;
}
for(i = 0;i < n;i++)
if(!mark[i])
c[k++] = c[i];
n = k;
}
//半径为r的圆，弧度为th对应的弓形的面积
double areaarc(double th,double r){
return 0.5*r*r*(th-sin(th));
}
//测试SPOJVCIRCLES SPOJCIRUT
//SPOJVCIRCLES求n个圆并的面积，需要加上init\_or()去掉重复圆（否则WA）
//SPOJCIRUT 是求被覆盖k次的面积，不能加init\_or()
//对于求覆盖多少次面积的问题，不能解决相同圆，而且不能init\_or()
//求多圆面积并，需要init\_or,其中一个目的就是去掉相同圆
void getarea(){
memset(ans,0,sizeof(ans));
vector<pair<double,int> >v;
for(int i = 0;i < n;i++){
v.clear();
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
for(int j = 0;j < n;j++)
if(i != j){
Point q = (c[j].p - c[i].p);
double ab = q.len(),ac = c[i].r, bc = c[j].r;
if(sgn(ab+ac-bc)<=0){
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(pi,-1));
continue;
}
if(sgn(ab+bc-ac)<=0)continue;
if(sgn(ab-ac-bc)>0)continue;
double th = atan2(q.y,q.x), fai = acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
double a0 = th-fai;
if(sgn(a0+pi)<0)a0+=2*pi;
double a1 = th+fai;
if(sgn(a1-pi)>0)a1-=2*pi;
if(sgn(a0-a1)>0){
v.push_back(make_pair(a0,1));
v.push_back(make_pair(pi,-1));
v.push_back(make_pair(-pi,1));
v.push_back(make_pair(a1,-1));
}
else{
v.push_back(make_pair(a0,1));
v.push_back(make_pair(a1,-1));
}
}
sort(v.begin(),v.end());
int cur = 0;
for(int j = 0;j < v.size();j++){
if(cur && sgn(v[j].first-pre[cur])){
ans[cur] += areaarc(v[j].first-pre[cur],c[i].r);
ans[cur] += 0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
}
cur += v[j].second;
pre[cur] = v[j].first;
}
}
for(int i = 1;i < n;i++)
ans[i] -= ans[i+1];
}
};

三维几何部分
代码：

const double eps = 1e-8;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point3{
double x,y,z;
Point3(double _x = 0,double _y = 0,double _z = 0){
x = _x;
y = _y;
z = _z;
}
void input(){
scanf("%lf%lf%lf",&x,&y,&z);
}
void output(){
scanf("%.2lf %.2lf %.2lf\n",x,y,z);
}
bool operator ==(const Point3 &b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
}
bool operator <(const Point3 &b)const{
return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
}
double len(){
return sqrt(x*x+y*y+z*z);
}
double len2(){
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const{
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
}
Point3 operator -(const Point3 &b)const{
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const{
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const{
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const{
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const{
return x*b.x+y*b.y+z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const{
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
Point3 p = (*this);
return acos( ( (a-p)*(b-p) )/ (a.distance(p)*b.distance(p)) );
}
//变换长度
Point3 trunc(double r){
double l = len();
if(!sgn(l))return *this;
r /= l;
return Point3(x*r,y*r,z*r);
}
};
struct Line3
{
Point3 s,e;
Line3(){}
Line3(Point3 _s,Point3 _e)
{
s = _s;
e = _e;
}
bool operator ==(const Line3 v)
{
return (s==v.s)&&(e==v.e);
}
void input()
{
s.input();
e.input();
}
double length()
{
return s.distance(e);
}
//点到直线距离
double dispointtoline(Point3 p)
{
return ((e-s)^(p-s)).len()/s.distance(e);
}
//点到线段距离
double dispointtoseg(Point3 p)
{
if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
return min(p.distance(s),e.distance(p));
return dispointtoline(p);
}
//返回点p在直线上的投影
Point3 lineprog(Point3 p)
{
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//p绕此向量逆时针arg角度
Point3 rotate(Point3 p,double ang)
{
if(sgn(((s-p)^(e-p)).len()) == 0)return p;
Point3 f1 = (e-s)^(p-s);
Point3 f2 = (e-s)^(f1);
double len = ((s-p)^(e-p)).len()/s.distance(e);
f1 = f1.trunc(len); f2 = f2.trunc(len);
Point3 h = p+f2;
Point3 pp = h+f1;
return h + ((p-h)*cos(ang)) + ((pp-h)*sin(ang));
}
//点在直线上
bool pointonseg(Point3 p)
{
return sgn( ((s-p)^(e-p)).len() ) == 0 && sgn((s-p)*(e-p)) == 0;
}
};
struct Plane
{
Point3 a,b,c,o;//平面上的三个点，以及法向量
Plane(){}
Plane(Point3 _a,Point3 _b,Point3 _c)
{
a = _a;
b = _b;
c = _c;
o = pvec();
}
Point3 pvec()
{
return (b-a)^(c-a);
}
//ax+by+cz+d = 0
Plane(double _a,double _b,double _c,double _d)
{
o = Point3(_a,_b,_c);
if(sgn(_a) != 0)
a = Point3((-_d-_c-_b)/_a,1,1);
else if(sgn(_b) != 0)
a = Point3(1,(-_d-_c-_a)/_b,1);
else if(sgn(_c) != 0)
a = Point3(1,1,(-_d-_a-_b)/_c);
}
//点在平面上的判断
bool pointonplane(Point3 p)
{
return sgn((p-a)*o) == 0;
}
//两平面夹角
double angleplane(Plane f)
{
return acos(o*f.o)/(o.len()*f.o.len());
}
//平面和直线的交点，返回值是交点个数
int crossline(Line3 u,Point3 &p)
{
double x = o*(u.e-a);
double y = o*(u.s-a);
double d = x-y;
if(sgn(d) == 0)return 0;
p = ((u.s*x)-(u.e*y))/d;
return 1;
}
//点到平面最近点(也就是投影)
Point3 pointtoplane(Point3 p)
{
Line3 u = Line3(p,p+o);
crossline(u,p);
return p;
}
//平面和平面的交线
int crossplane(Plane f,Line3 &u)
{
Point3 oo = o^f.o;
Point3 v = o^oo;
double d = fabs(f.o*v);
if(sgn(d) == 0)return 0;
Point3 q = a + (v*(f.o*(f.a-a))/d);
u = Line3(q,q+oo);
return 1;
}
};

平面最近点对
代码：

const int MAXN = 100010;
const double eps = 1e-8;
const double INF = 1e20;
struct Point{
double x,y;
void input(){
scanf("%lf%lf",&x,&y);
}
};
double dist(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Point p[MAXN];
Point tmpt[MAXN];
bool cmpx(Point a,Point b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cmpy(Point a,Point b){
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
double Closest_Pair(int left,int right){
double d = INF;
if(left == right)return d;
if(left+1 == right)return dist(p[left],p[right]);
int mid = (left+right)/2;
double d1 = Closest_Pair(left,mid);
double d2 = Closest_Pair(mid+1,right);
d = min(d1,d2);
int cnt = 0;
for(int i = left;i <= right;i++){
if(fabs(p[mid].x - p[i].x) <= d)
tmpt[cnt++] = p[i];
}
sort(tmpt,tmpt+cnt,cmpy);
for(int i = 0;i < cnt;i++){
for(int j = i+1;j < cnt && tmpt[j].y - tmpt[i].y < d;j++)
d = min(d,dist(tmpt[i],tmpt[j]));
}
return d;
}
int main(){
int n;
while(scanf("%d",&n) == 1 && n){
for(int i = 0;i < n;i++)p[i].input();
sort(p,p+n,cmpx);
printf("%.2lf\n",Closest_Pair(0,n-1));
}
return 0;
}

三维凸包
代码：

const double eps = 1e-8;
const int MAXN = 550;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point3{
double x,y,z;
Point3(double _x = 0, double _y = 0, double _z = 0){
x = _x;
y = _y;
z = _z;
}
void input(){
scanf("%lf%lf%lf",&x,&y,&z);
}
bool operator ==(const Point3 &b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
}
double len(){
return sqrt(x*x+y*y+z*z);
}
double len2(){
return x*x+y*y+z*z;
}
double distance(const Point3 &b)const{
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
}
Point3 operator -(const Point3 &b)const{
return Point3(x-b.x,y-b.y,z-b.z);
}
Point3 operator +(const Point3 &b)const{
return Point3(x+b.x,y+b.y,z+b.z);
}
Point3 operator *(const double &k)const{
return Point3(x*k,y*k,z*k);
}
Point3 operator /(const double &k)const{
return Point3(x/k,y/k,z/k);
}
//点乘
double operator *(const Point3 &b)const{
return x*b.x + y*b.y + z*b.z;
}
//叉乘
Point3 operator ^(const Point3 &b)const{
return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
}
};
struct CH3D{
struct face{
//表示凸包一个面上的三个点的编号
int a,b,c;
//表示该面是否属于最终的凸包上的面
bool ok;
};
//初始顶点数
int n;
Point3 P[MAXN];
//凸包表面的三角形数
int num;
//凸包表面的三角形
face F[8*MAXN];
int g[MAXN][MAXN];
//叉乘
Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c){
return (b-a)^(c-a);
}
//三角形面积*2
double area(Point3 a,Point3 b,Point3 c){
return ((b-a)^(c-a)).len();
}
//四面体有向面积*6
double volume(Point3 a,Point3 b,Point3 c,Point3 d){
return ((b-a)^(c-a))*(d-a);
}
//正：点在面同向
double dblcmp(Point3 &p,face &f){
Point3 p1 = P[f.b] - P[f.a];
Point3 p2 = P[f.c] - P[f.a];
Point3 p3 = p - P[f.a];
return (p1^p2)*p3;
}
void deal(int p,int a,int b){
int f = g[a][b];
if(F[f].ok){
if(dblcmp(P[p],F[f]) > eps)
dfs(p,f);
else {
g[p][b] = g[a][p] = g[b][a] = num;
}
}
}
//递归搜索所有应该从凸包内删除的面
void dfs(int p,int now){
F[now].ok = false;
deal(p,F[now].b,F[now].a);
deal(p,F[now].c,F[now].b);
deal(p,F[now].a,F[now].c);
}
bool same(int s,int t){
Point3 &a = P[F[s].a];
Point3 &b = P[F[s].b];
Point3 &c = P[F[s].c];
return fabs(volume(a,b,c,P[F[t].a])) < eps &&
fabs(volume(a,b,c,P[F[t].b])) < eps &&
fabs(volume(a,b,c,P[F[t].c])) < eps;
}
//构建三维凸包
void create(){
num = 0;

//***********************************
//此段是为了保证前四个点不共面
bool flag = true;
for(int i = 1;i < n;i++){
if(!(P[0] == P[i])){
swap(P[1],P[i]);
flag = false;
break;
}
}
if(flag)return;
flag = true;
for(int i = 2;i < n;i++){
if( ((P[1]-P[0])^(P[i]-P[0])).len() > eps ){
swap(P[2],P[i]);
flag = false;
break;
}
}
if(flag)return;
flag = true;
for(int i = 3;i < n;i++){
if(fabs( ((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]) ) > eps){
swap(P[3],P[i]);
flag = false;
break;
}
}
if(flag)return;
//**********************************

for(int i = 0;i < 4;i++){
}
for(int i = 4;i < n;i++)
for(int j = 0;j < num;j++)
if(F[j].ok && dblcmp(P[i],F[j]) > eps){
dfs(i,j);
break;
}
int tmp = num;
num = 0;
for(int i = 0;i < tmp;i++)
if(F[i].ok)
F[num++] = F[i];
}
//表面积
//测试：HDU3528
double area(){
double res = 0;
if(n == 3){
Point3 p = cross(P[0],P[1],P[2]);
return p.len()/2;
}
for(int i = 0;i < num;i++)
res += area(P[F[i].a],P[F[i].b],P[F[i].c]);
return res/2.0;
}
double volume(){
double res = 0;
Point3 tmp = Point3(0,0,0);
for(int i = 0;i < num;i++)
res += volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
return fabs(res/6);
}
//表面三角形个数
int triangle(){
return num;
}
//表面多边形个数
//测试：HDU3662
int polygon(){
int res = 0;
for(int i = 0;i < num;i++){
bool flag = true;
for(int j = 0;j < i;j++)
if(same(i,j)){
flag = 0;
break;
}
res += flag;
}
return res;
}
//重心
//测试：HDU4273
Point3 barycenter(){
Point3 ans = Point3(0,0,0);
Point3 o = Point3(0,0,0);
double all = 0;
for(int i = 0;i < num;i++){
double vol = volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
ans = ans + (((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
all += vol;
}
ans = ans/all;
return ans;
}
//点到面的距离
//测试：HDU4273
double ptoface(Point3 p,int i){
double tmp1 = fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
double tmp2 = ((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
return tmp1/tmp2;
}
};
CH3D hull;
int main()
{
while(scanf("%d",&hull.n) == 1){
for(int i = 0;i < hull.n;i++)hull.P[i].input();
hull.create();
Point3 p = hull.barycenter();
double ans = 1e20;
for(int i = 0;i < hull.num;i++)
ans = min(ans,hull.ptoface(p,i));
printf("%.3lf\n",ans);
}
return 0;
}

转载于:https://www.cnblogs.com/Staceyacm/p/10797445.html
展开全文
• POJ 2318 TOYS 题意：m个玩具落在n+1个区间，给你玩具的坐标，问每个区间有多少玩具。 思路：叉积的简单应用，用叉积判断在直线的哪一侧，因为是顺序给出坐标，所以从左往右判断即可。 ...cma...
• （为了套板子，写的很繁琐） 2.poj2007 Scrambled Polygon 题目： http://poj.org/problem?id=2007 题意：求一个凸多边形的凸包。要求起始点为输入的第一个点。 分析：rt。 1 #include 2 #include...
• 大菜鸡的计算几何之旅-[kuangbin带你飞]专题十三 基础计算几何 A POJ 2318 TOYS Description Calculate the number of toys that land in each bin of a partitioned toy box. Mom and dad have a problem - their ...
• 1.poj3335Rotating Scoreboard ... 题意：就是有个球场，球场的形状是个凸多边形，然后观众是坐在多边形的边上的，问你是否在球场上有个地方可以放一个记分牌，然后所有的观众都可以看得到的。 分析：多边形是否存在...
• 不要过分相信的我抄的，我在用的时候也经常会遇到错，所以如果不对，还请自己改，或者自己找一份原kuangbin大佬的计算几何板子。 # include using namespace std ; # define me(x,y) memset(x,y,sizeof x)...
• 附上做这套专题的模板（该专题只有点线面的关系所以这些模板就够了） const db EPS=1e-9; inline int sign(db a){return a&lt;-EPS?-1:a&gt;EPS;} inline int cmp(db a,db b){return sign(a-b);...
• 这两天要花时间研究一下kuangbin计算几何模板，至少我要知道该怎么用才可以。 ac code #include <bits/stdc++.h> #define pb push_back #define ld long double using namespace std; cons
• ACM Template of kuangbin 3 数据结构 56 3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
• 下面给出两种不同风格的代码，一种是网上找的，便于理解，一种是从kuangbin模板上摘下来的，适用性更广，可以当作板子用。其中对于给出点的顺时针和逆时针顺序不同，邝斌模板只需要加个 reverse 函数将点的顺序颠倒...
• 计算几何是直接可以拿kuangbin板子进行写的，但是还是需要有自己的一些储备。 方法：从平面几何->解析几何 首先，我们需要判断浮点数符号。 const double eps = 1e-8; //... int sgn(double x) { if (fabs(x) ...
• kuangbin板子 int sgn(double x) { //符号函数 if (fabs(x) < eps) return 0; if (x < 0) return -1; else return 1; } struct Point { //点 double x, y; Point() { } Point(double _x, double _...
• 计算几何的题还是写的少，调了一个小时的蜜汁bug最后发现被卡精度了，得用long double，这题思路上并不难，先判断一下直线AV是否与圆的交点个数，如果少于2个交点，判断B是否在射线AV上，如果有两个交点，求出距离A...
• 找到适合的模板 前期用kuangbin板子磕磕绊绊敲题 现在用经诗姐姐的板子（感谢经诗姐姐！）后期研究出适合自己手感的板子（自己造板子） 千万千万不要敲错板子！！ 在大量计算过程中注意精度控制 如果wa了要考虑...
• 自己的板子积累,不断更新中 数学 欧拉筛(线性筛) 时间复杂度O(n) void prime(int n) { for(int i=2; i<=n; i++) { if(!st[i]) p[ans++]=i; for(int j=0; p[j]<=n/i; j++) { st[p[j]*i]=1; if(i%...
• 代码： 注：直接套了kuangbin计算几何板子，很长 #include #include #include #include #include using namespace std; const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const...
• 判断线段和直线相交可以用kuangbin板子，我解斜截式直线方程，分斜率是否存在讨论。 /* Author : Rshs */ #include<bits/stdc++.h> using namespace std; #define FI first #define SE second #define LL ...
• 文章目录专题十三 基础计算几何POJ 2318 TOYSPOJ 2398 Toy StoragePOJ 3304 SegmentsPOJ 1269 Intersecting LinesPOJ 1556 The DoorsPOJ 2653 Pick-up sticksPOJ 1066 Treasure HuntPOJ 1410 IntersectionPOJ 1696 ...
• here 要在n个点中选中4个点求一个矩形的最大面积。 如果枚举点的话复杂度实在太高了...kuangbin板子还是看着不太习惯，这几天适应一下吧！下边是我自己写的不是他的板子。 ac code //god with me #include <bits/s
• 解释与代码 kuangbin板子 真就无脑暴力呗,正好卡在时限内,再多一点就超时了 #include #include #include #include #include #include #include #include #include #include #include #include #include #include ...
• //要看一下是否在线段上，因为有可能求出的点在延长线上 if(l[i].pointonseg1(temp)){ //这里要吐槽一下kuangbin大神的板子，好像只能判断是否在直线上，并不能判断是否在线段上 //所以，我又写了个函数判断求得点...
• kuangbin 大大的板子（侵删） 这道题首先可以确认的是最远点对一定在凸包上。 求出凸包以后，作两点的平行线，当一点到平行线的方向发生改变时达到可能的最大值（旋转卡壳）。然后旋转到每个点都考虑完毕就可以...
• 直接用kuangbin板子，能判不规范，规范和不交 另外线段在矩形内也可以，判断方式是比较线段的端点和矩形四个角 #include <cstdio> #include <cmath> #include <algorithm> #include <...
• 前一段时间做了kuangbin带你飞基础数论专题部分，可看了不少的相关的资料，在这里也来做一个总结。 由于数论方面的知识太多...杜教筛等等还没学）的汇总，关于数论的板子等学完计算几何和组合数学之后找个时间再汇...