[HAOI2008]下落的圆盘

C++14(g++5.4) 解法, 执行用时: 34ms, 内存消耗: 608K, 提交时间: 2020-04-11 23:34:09

//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const double eps = 1e-10;
const int MAXN=1005;
//const double PI=acos(-1);
double pi=acos(-1.0);
int sgn(double d)
{
    return d<-eps?-1:d>eps;
}
int dcmp(double x) //减少精度问题
{
    if(fabs(x) < eps)
        return 0;
    if(x < 0)
        return -1;
    return 1;
}
struct Point //点定义
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {}
};
typedef Point Vector;

Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator-(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator*(Vector A,double p)
{
    return Vector(A.x*p,A.y*p);
}
Vector operator/(Vector A,double p)
{
    return Vector(A.x/p,A.y/p);
}

bool operator < (const Point& a, const Point& b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
bool operator == (const Point& a, const Point& b)
{
    if(dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0)
        return true;
    return false;
}

double Dot(Vector A, Vector B) //向量内积，求的是夹角为锐角还是钝角，点乘
{
    return A.x*B.x + A.y*B.y;
}

double Cross(Vector A, Vector B) //向量外积，判断A和B哪个在前（>0,B在A逆时针方向），A、B是否共线等。
{
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A) //长度
{
    return sqrt(Dot(A, A));
}

double Angle(Vector A, Vector B) //返回值为弧度制下的夹角，由内积得到
{
    return acos(Dot(A, B) / Length(A) / Length(B));
}
double Area2(Point A, Point B, Point C) //计算两向量构成的平行四边形有向面积，由外积得到
{
    return Cross(B-A, C-A);
}
Vector Rotate(Vector A, double rad) //rad为弧度 且为逆时针旋转的角，计算向量逆时针旋转后的向量
{
    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A) //向量A左转90°的单位法向量，计算向量逆时针旋转九十度的单位法向量
{
    double L = Length(A);
    return Vector(-A.y/L, A.x/L);
}
bool ToLeftTest(Point a, Point b, Point c) //判断折线bc是不是向ab的逆时针方向（左边）转向
{
    return Cross(b - a, c - b) > 0;
}
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) //计算两直线交点
{
    Vector u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}

double DistanceToLine(Point P, Point A, Point B) //计算点P到直线的距离
{
    Vector v1 = B-A, v2 = P-A;
    return fabs(Cross(v1, v2)/Length(v1));
}


double DistanceToSegment(Point P, Point A, Point B) //计算点P到线段AB距离公式
{
    if(A == B)
        return Length(P-A);
    Vector v1 = B-A, v2 = P-A, v3 = P-B;
    if(dcmp(Dot(v1, v2)) < 0)
        return Length(v2);
    if(dcmp(Dot(v1, v3)) > 0)
        return Length(v3);
    return DistanceToLine(P, A, B);
}

Point GetLineProjection(Point P, Point A, Point B) //点P在直线AB上的投影点
{
    Vector v = B-A;
    return A+v*(Dot(v, P-A)/Dot(v, v));
}
struct Circle
{
    double l,r;
};
Circle a[MAXN];

int n;
double x[MAXN],y[MAXN],r[MAXN];
double ans;
bool cmp(Circle a,Circle b)
{
    return a.l<b.l;
}
double dist(int i,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
bool contain(int i,int j)//i完全覆盖了j圆，则返回1
{
    if (r[i]-r[j]>=dist(i,j))
        return 1;
    return 0;
}
double cal(int k)
{
    int num=0;
    for (int i=k+1; i<=n; i++)
        if (contain(i,k))//被覆盖了，长度位0
            return 0;
    for (int i=k+1; i<=n; i++)
    {
        if (contain(k,i)||dist(k,i)>=r[i]+r[k])
            continue;
        double d=dist(k,i);
        double ac=acos((-r[i]*r[i]+r[k]*r[k]+d*d)/(2.0*d*r[k]));
        double conta=atan2(y[i]-y[k],x[i]-x[k]);
        Circle l={conta-ac,conta+ac};
        a[++num]=l;
        if (a[num].l<0)
        {
             a[num].l+=2*pi;
        }

        if (a[num].r<0)
        {
            a[num].r+=2*pi;
        }

        if (a[num].l>a[num].r)
        {
            double p=a[num].l;
            a[num].l=0;
            a[++num].l=p;
            a[num].r=2*pi;
        }
    }
    sort(a+1,a+num+1,cmp);
    double res=0.0,now=0.0;
    for (int i=1; i<=num; i++)
    {
        if (a[i].l>now)
            res+=a[i].l-now,now=a[i].r;
        now=max(now,a[i].r);
    }
    res+=2*pi-now;
    return res*r[k];
}
int main()
{
    cin>>n;
    ans=0.0;
    for (int i=1; i<=n; i++)
    {
        cin>>r[i]>>x[i]>>y[i];
    }
    for (int i=1; i<=n-1; i++)
        ans+=cal(i);
    ans+=2*pi*r[n];//最后一个绝对没被覆盖
    printf("%.3lf\n",ans);
}

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 15ms, 内存消耗: 464K, 提交时间: 2023-08-12 15:44:03

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1010
#define eps 1e-9
#define MAXDBL 1e20
#define pi acos(-1)
using namespace std;
int n,top;
double ans,sum,temp;
struct Bug
{
    double lb,rb;
    bool operator <(const Bug& a)const
    {
        return lb!=a.lb?lb<a.lb:rb<a.rb;
    }
}sta[MAXN];
struct circle
{
    double x,y,r;
}s[MAXN];
inline double sqr(double x)
{
    return x*x;
}
inline double dis(circle a,circle b)
{
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
inline bool in(circle a,circle b)
{
    return a.r>=b.r+dis(a,b);
}
inline void circle_cross_circle(circle a,circle b)
{
    double Dis=dis(a,b),tmp,st,bugle;
    tmp=(sqr(a.r)-sqr(b.r)+sqr(Dis))/(Dis*2);
    st=atan2((a.x-b.x),(a.y-b.y));
    bugle=acos(tmp/a.r);
    sta[++top]=(Bug){(st-bugle),(st+bugle)};
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)  scanf("%lf%lf%lf",&s[i].r,&s[i].x,&s[i].y);
    for (int i=1;i<=n;i++)  
    {
        top=0;sum=0;temp=0;
        bool flag=0;
        for (int j=i+1;j<=n;j++)
            if (in(s[j],s[i]))
            {
                flag=1;
                break;
            }
        if (flag)   continue;
        for (int j=i+1;j<=n;j++)
            if (!in(s[i],s[j])&&s[i].r+s[j].r>=dis(s[i],s[j]))  circle_cross_circle(s[i],s[j]);
        for (int j=1;j<=top;j++)
        {
            while (sta[j].lb<0) sta[j].lb+=2*pi;
            while (sta[j].rb<0) sta[j].rb+=2*pi;
            if (sta[j].lb>sta[j].rb)    sta[++top]=(Bug){0,sta[j].rb},sta[j].rb=2*pi;
        }
        sort(sta+1,sta+top+1);
        for (int j=1;j<=top;j++)
            if (sta[j].lb>temp) sum+=sta[j].lb-temp,temp=sta[j].rb;
            else temp=max(temp,sta[j].rb);
        sum+=2*pi-temp;
        ans+=s[i].r*sum;
    }
    printf("%.3f\n",ans);
}

C++(clang++11) 解法, 执行用时: 49ms, 内存消耗: 496K, 提交时间: 2022-10-27 07:45:18

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

const double PI = acos(-1);
const double PI2 = PI * 2;
const int MAXN = 1010;
const double eps = 1e-6;
int n;
double xs[MAXN], ys[MAXN], rs[MAXN];
typedef std::pair<double, double> PDD;
PDD cover[MAXN]; int bak;
inline double pows(double x) { return x * x; }
inline double absx(double x) { return x < 0 ? -x : x; }
inline double reduce(double x) { x += PI2, x = x - (int) (x / PI2) * PI2; return x; }
int main() {
	scanf("%d", &n);
	double ans = 0;
	for (int i = 1; i <= n; ++i)
		scanf("%lf%lf%lf", rs + i, xs + i, ys + i);
	for (int i = 1; i <= n; ++i) {
		bak = 0;
		for (int j = i + 1; j <= n; ++j) {
			double D = sqrt(pows(xs[i] - xs[j]) + pows(ys[i] - ys[j]));
			if (D >= absx(rs[i] + rs[j]) - eps) continue;
			if (D <= absx(rs[i] - rs[j]) + eps) {
				if (rs[j] > rs[i])
					cover[++bak] = PDD(0, PI2);
				continue;
			}
			double y = (D - (pows(rs[j]) - pows(rs[i])) / D) / 2;
			double angle = acos(y / rs[i]);
			double oa = reduce(atan2(xs[i] - xs[j], ys[i] - ys[j]) + PI / 2);
			double L = reduce(oa - angle), R = reduce(oa + angle);
			if (L - eps > R) cover[++bak] = PDD(L, PI2), cover[++bak] = PDD(0, R);
			else cover[++bak] = PDD(L, R);
		}
		std::sort(cover + 1, cover + 1 + bak);
		ans += PI2 * rs[i];
		double lstl = 0, lstr = 0;
		for (int j = 1; j <= bak; ++j) {
			const double fx = cover[j].first, sx = cover[j].second;
			if (fx > lstr) {
				ans -= (lstr - lstl) * rs[i];
				lstl = fx;
			}
			lstr = std::max(lstr, sx);
		}
		ans -= (lstr - lstl) * rs[i];
	}
	printf("%.3lf\n", ans);
	return 0;
}

详情