?

多校第十场的一道几何，做了好久了，忘了发出来。比赛的时候由于坑爹的模板，后台100组数据错了一组，导致比赛的时候没做出来，赛后郁闷了好久。。。。。比赛之后好好整了一下凸包的模板，代码里会是Graham算法，标程用的是Andrew算法。

?

题目大意:一个无限大的平面上，有间距为D的无限条水平直线，如图所示。

给你一个直径为D的硬币，硬币中有n个点，每两个点之间都有一条线段，任意三点不会共线。随机的将硬币扔到上图中的平面内，问至少有一条线段跟平面内的直线相交的概率是多少。

?

解题思路：很容易想到的是，对于硬币上的所有点来说，无疑是构成一个凸包的时候为所求的情况，而当点的个数为1的时候，概率为0。

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const double eps = 1e-6; const double Pi = acos(-1.0); #define zero(x) (((x) > 0 ? (x) : (-x)) < eps) int q, n; struct Point { double x,y; Point() {} Point(double _x,double _y) { x = _x; y = _y; } 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; //绕原点旋转角度B（弧度值），后x,y的变化 } void transXY(double B) { double tx = x,ty = y; x = tx*cos(B) - ty*sin(B); y = tx*sin(B) + ty*cos(B); } } P[105], ch[105]; double Distance(Point a, Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double xmult(Point p1, Point p2, Point p){ return (p1.x-p.x)*(p2.y-p.y) - (p1.y-p.y)*(p2.x-p.x); } int dcmp(double x){ return fabs(x)
      
        0; } } int Graham(int n){ int s = 0, top = 1; for(int i = 0; i < n; ++i){ if(P[i].y < P[s].y || (P[i].y == P[s].y && P[i].x < P[s].x)){ s = i; } } if(s != 0){ Point tmp = P[0]; P[0] = P[s]; P[s] = tmp; } sort(P+1, P+n, cmp); ch[0] = P[0], ch[1] = P[1]; for(int i = 2; i < n; ++i){ while(top > 0 && dcmp(xmult(ch[top], P[i], ch[top-1])) < 0){ top--; } ch[++top] = P[i]; } return top+1; } int T; double d; int main() { //freopen(1008.in, r, stdin); //freopen(data.out, w, stdout); int icase = 1; scanf(%d, &T); while(T--){ scanf(%d%lf, &n, &d); for(int i = 0; i < n; ++i){ scanf(%lf%lf, &P[i].x, &P[i].y); } printf(Case #%d: , icase++); if(n >= 3){ int t = Graham(n); //printf(%d , t); double sum = Distance(ch[0], ch[t-1]); for(int i = 0; i < t-1; ++i){ sum += Distance(ch[i], ch[i+1]); } //printf(q = %d , q); //printf(%lf , Area()); //printf(%lf ,sum); printf(%.4lf , sum/(Pi*(d))); } else if(n == 2){ double dis = Distance(P[0], P[1]); printf(%.4lf , 2*dis/(Pi*d)); } else { printf(0.0000 ); } //printf(%lf %lf , Min.y, Max.y); } return 0; } /* 100 3 3 0 1 1 0 -1 0 */
      
     
    
   
  

?