QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244335#7027. Machining Disc RotorsyiyiyiWA 68ms4076kbC++205.5kb2023-11-08 23:13:592023-11-08 23:14:00

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 23:14:00]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:4076kb
  • [2023-11-08 23:13:59]
  • 提交

answer

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#include<set> 
#define ll long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define forE(i,x) for(int i=head[x];i;i=nxt[i])
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+5;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*f;
}
using point_t=long double;  //全局数据类型,可修改为 long long 等

constexpr point_t eps=1e-8;
constexpr long double PI=3.1415926535897932384l;

// 点与向量
template<typename T> struct point
{
    T x,y;

    bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
    bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
    bool operator>(const point &a) const {return !(*this<a || *this==a);}
    point operator+(const point &a) const {return {x+a.x,y+a.y};}
    point operator-(const point &a) const {return {x-a.x,y-a.y};}
    point operator-() const {return {-x,-y};}
    point operator*(const T k) const {return {k*x,k*y};}
    point operator/(const T k) const {return {x/k,y/k};}
    T operator*(const point &a) const {return x*a.x+y*a.y;}  // 点积
    T operator^(const point &a) const {return x*a.y-y*a.x;}  // 叉积,注意优先级
    int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);}  // 向量与向量的to-left 测试 1left -1right 0on
    T len2() const {return (*this)*(*this);}  // 向量长度的平方
    T dis2(const point &a) const {return (a-(*this)).len2();}  // 两点距离的平方

    // 涉及浮点数
    long double len() const {return sqrtl(len2());}  // 向量长度
    long double dis(const point &a) const {return sqrtl(dis2(a));}  // 两点距离
    long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));}  // 向量夹角
    point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}  // 逆时针旋转(给定角度)
    point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};}  // 逆时针旋转(给定角度的正弦与余弦)
};

using Point=point<point_t>;

// 圆
struct Circle
{
    Point c;
    long double r;

    bool operator==(const Circle &a) const {return c==a.c && abs(r-a.r)<=eps;}
    long double circ() const {return 2*PI*r;}  // 周长
    long double area() const {return PI*r*r;}  // 面积


    // 圆与圆关系
    // -1 相同 | 0 相离 | 1 外切 | 2 相交 | 3 内切 | 4 内含
    int relation(const Circle &a) const
    {
        if (*this==a) return -1;
        const long double d=c.dis(a.c);
        if (d>r+a.r+eps) return 0;
        if (abs(d-r-a.r)<=eps) return 1;
        if (abs(d-abs(r-a.r))<=eps) return 3;
        if (d<abs(r-a.r)-eps) return 4;
        return 2;
    }

    // 圆与圆交点
    vector<Point> inter(const Circle &a) const
    {
        const long double d=c.dis(a.c);
        const int t=relation(a);
        if (t==-1 || t==0 || t==4) return vector<Point>();
        Point e=a.c-c; e=e/e.len()*r;
        if (t==1 || t==3) 
        {
            if (r*r+d*d-a.r*a.r>=-eps) return vector<Point>{c+e};
            return vector<Point>{c-e};
        }
        const long double costh=(r*r+d*d-a.r*a.r)/(2*r*d),sinth=sqrt(1-costh*costh);
        return vector<Point>{c+e.rot(costh,-sinth),c+e.rot(costh,sinth)};
    }
};

bool cmp(pair<Point,int> u,pair<Point,int> v)
{
    Point a=u.first,b=v.first;
    const auto quad=[](const Point a)
    {
        if (a.y<-eps) return 1;
        if (a.y>eps) return 4;
        if (a.x<-eps) return 5;
        if (a.x>eps) return 3;
        return 2;
    };
    const int qa=quad(a),qb=quad(b);
    if (qa!=qb) return qa<qb;
    const auto t=a^b;
    // if (abs(t)<=eps) return a*a<b*b-eps;  // 不同长度的向量需要分开
    return t>eps;
}

Circle O,c[maxn];
Point o={0,0};
vector<pair<Point,int>> e;
signed main()
{
    int T=read();
    rep(P,1,T)
    {
        printf("Case #%lld: ",P);
        int n=read(),R=read();
        e.clear();
        O={{0,0},(long double)R};
        rep(i,1,n) c[i]={{(point_t)read(),(point_t)read()},(point_t)read()};
        rep(i,1,n)
        {
            auto v = O.inter(c[i]);
            if((int)v.size() != 2) continue;
            Point x = v[0]-c[i].c, y = v[1]-c[i].c;
            if(x.toleft(y)==1) swap(v[0],v[1]);
            e.push_back({v[0],0});e.push_back({v[1],1});
        }
        sort(e.begin(),e.end(),cmp);
        long double ans=0.0;
        for(auto i:e)
        {
            for(auto j:e)
            {
                Point x = i.first, y = j.first;
                ans=max(ans,x.dis(y));
            }
            Point x = i.first;
            Point rev = -x;
            auto it = lower_bound(e.begin(),e.end(),make_pair(rev,0),cmp);
            auto pre = it;
            if(pre == e.begin()) pre=e.end(),pre--;
            else pre--;
            if(it == e.end()) it = e.begin();
            if(it->second == 0 && pre->second == 1) ans=max(ans,O.r+O.r);
        }
        printf("%.15Lf\n",ans);
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

1
3 10
0 12 10
11 -6 10
-11 -6 10

output:

Case #1: 18.611654895000252

result:

ok 1 cases

Test #2:

score: -100
Wrong Answer
time: 68ms
memory: 4076kb

input:

5000
3 1000
750 500 625
-250 -625 625
-1000 1000 1000
3 8
-6 -4 5
2 5 5
8 -8 8
1 710
426 -568 994
1 10
-8 6 15
14 931
622 -651 207
-930 438 552
931 890 743
-264 -923 671
889 -315 179
15 761 173
-440 883 81
-938 -310 170
-271 981 91
918 -88 47
136 927 26
903 29 61
-162 936 22
917 129 18
32 595
431 11...

output:

Case #1: 2000.000000000000000
Case #2: 16.000000000000000
Case #3: 1420.000000000000000
Case #4: 19.843134832984429
Case #5: 1862.000000000000000
Case #6: 1190.000000000000000
Case #7: 934.000000000000000
Case #8: 542.000000000000000
Case #9: 1808.000000000000000
Case #10: 1472.000000000000000
Case ...

result:

wrong answer In case 1, expected '1998.628237512163', but found '2000.000000000000', error '0.000685881244'.