Peter and Snow Blower CodeForces - 613A (点到线段距离)

柔光的暖阳◎ 2021-11-05 22:31 369阅读 0赞

大意: 给定多边形, 给定点$P$, 求一个以$P$为圆心的最小的圆环包含整个多边形.

#include <iostream>
    #include <cmath>
    #define REP(i,a,b) for(int i=a;i<=b;i++)
    
    const double eps=1e-8;
    
    int dcmp(double x) {return fabs(x)<=eps?0:x>eps?1:-1;}
    
    const int N = 1e5+10;
    struct Point {
    	double x,y;
    	Point(double x=0,double y=0):x(x),y(y) {}
    	Point operator + (const Point &a) {return Point(x+a.x,y+a.y);}
    	Point operator - (const Point &a) {return Point(a.x-x,a.y-y);}
    	Point operator * (double a) {return Point(x*a,y*a);}
    	Point operator / (double a) {return Point(x/a,y/a);}
    	bool operator < (const Point &b) const {return x<b.x||(x==b.x&&y<b.y);}
    	bool operator == (Point b) {return dcmp(x-b.x)==0&&dcmp(y-b.y)==0;}
    	double length() {return sqrt(x*x+y*y);}
    	Point rotate(double rad) {return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));}
    	Point normal(Point a) {return Point(-a.y/a.length(),a.x/a.length());}
    } a[N];
    
    typedef Point Vector;
    
    double Cross(const Vector& a,const Vector& b) {return a.x*b.y-b.x*a.y;}
    double Dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}
    double Angle(Vector a,Vector b) {return acos(Dot(a,b)/a.length()/b.length());}
    double Area(Point a,Point b,Point c) {return Cross(b-a,c-a);}
    
    bool OnSegment(Point p,Point a,Point b) {return dcmp(Cross(a-p,b-p))==0&&dcmp(Dot(a-p,b-p))<0;}
    bool Segment_Intersection(Point a1,Point a2,Point b1,Point b2) {return dcmp(Cross(a2-a1,b1-a1))*dcmp(Cross(a2-a1,b2-a1))<0&&dcmp(Cross(b2-b1,a1-b1))*dcmp(Cross(b2-b1,a2-b1))<0;}
    Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) {return P+v*(Cross(P-Q,w)/Cross(v,w));}
    double DistanceToLine(Point p,Point a,Point b) {Vector v1=b-a,v2=p-a;return fabs(Cross(v1,v2))/v1.length();}
    double DistanceToSegment(Point p,Point a,Point b) {
    	if(a==b)return (p-a).length();
    	Vector v1=b-a,v2=p-a,v3=p-b;
    	if(dcmp(Dot(v1,v2))<0)return v2.length();
    	else if(dcmp(Dot(v1,v3))>0)return v3.length();
    	else return DistanceToLine(p,a,b);
    }
    
    double Area(int n,Point* P) {
    	double ans=0;
    	for(int i=2; i<n; i++)ans+=Area(P[1],P[i],P[i+1]);
    	return ans/2;
    }
    
    int main() {
    	int n,x,y;
    	scanf("%d%d%d", &n, &x, &y);
    	double mi = 1e18, ma = -1e18;
    	REP(i,1,n) {
    		int xx, yy;
    		scanf("%d%d", &xx, &yy);
    		a[i]=Point(xx-x,yy-y);
    		ma=max(ma,a[i].length());
    	}
    	REP(i,2,n) mi=fmin(mi,DistanceToSegment(Point(),a[i],a[i-1]));
    	mi=fmin(mi,DistanceToSegment(Point(),a[n],a[1]));
    	printf("%.12lf\n",acos(-1)*(ma*ma-mi*mi));
    }

转载于:https://www.cnblogs.com/uid001/p/10853127.html