QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152055#6118. EartheartSommohitoWA 1ms4004kbC++207.2kb2023-08-27 16:13:582023-08-27 16:13:59

Judging History

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

  • [2023-08-27 16:13:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4004kb
  • [2023-08-27 16:13:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef IFT
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()

const long double eps=1e-3;

inline int dcmp (long double x)
{
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

struct PT
{
    long double x, y;
    PT (long double x = 0, long double y = 0): x(x), y(y) {}
    void read ()
    {
        scanf("%lf%lf", &x, &y);
    }
    void write ()
    {
        printf("%lf %lf", x, y);
    }
    bool operator == (const PT& u) const
    {
        return dcmp(x - u.x) == 0 && dcmp(y - u.y) == 0;
    }
    bool operator != (const PT& u) const
    {
        return !(*this == u);
    }
    bool operator < (const PT& u) const
    {
        return dcmp(x - u.x) < 0 || (dcmp(x-u.x)==0 && dcmp(y-u.y) < 0);
    }
    bool operator > (const PT& u) const
    {
        return u < *this;
    }
    bool operator <= (const PT& u) const
    {
        return *this < u || *this == u;
    }
    bool operator >= (const PT& u) const
    {
        return *this > u || *this == u;
    }
    PT operator + (const PT& u)
    {
        return PT(x + u.x, y + u.y);
    }
    PT operator - (const PT& u)
    {
        return PT(x - u.x, y - u.y);
    }
    PT operator * (const long double u)
    {
        return PT(x * u, y * u);
    }
    PT operator / (const long double u)
    {
        return PT(x / u, y / u);
    }
    long double operator * (const PT& u)
    {
        return x*u.y - y*u.x;
    }
};

inline long double cross(PT a, PT b)
{
    return a.x * b.y - a.y * b.x;
}
inline long double cross2(PT a, PT b, PT c)
{
    return cross(b - a, c - a);
}

bool is_point_on_seg(PT a, PT b, PT p)
{
    if (fabs(cross(p - b, a - b)) < eps)
    {
        if (p.x < min(a.x, b.x) || p.x > max(a.x, b.x)) return false;
        if (p.y < min(a.y, b.y) || p.y > max(a.y, b.y)) return false;
        return true;
    }
    return false;
}
bool seg_seg_intersection(PT a, PT b, PT c, PT d, PT &ans)
{
    long double oa = cross2(c, d, a), ob = cross2(c, d, b);
    long double oc = cross2(a, b, c), od = cross2(a, b, d);
    if (oa * ob < 0 && oc * od < 0)
    {
        ans = (a * ob - b * oa) / (ob - oa);
        return 1;
    }
    else return 0;
}
set<PT> seg_seg_intersection_inside(PT a,  PT b,  PT c,  PT d)
{
    PT ans;
    if (seg_seg_intersection(a, b, c, d, ans)) return {ans};
    set<PT> se;
    if (is_point_on_seg(c, d, a)) se.insert(a);
    if (is_point_on_seg(c, d, b)) se.insert(b);
    if (is_point_on_seg(a, b, c)) se.insert(c);
    if (is_point_on_seg(a, b, d)) se.insert(d);
    return se;
}
#define Pt PT
#define Vector PT
struct Circle
{
    Pt o;
    long double r;
    Circle () {}
    Circle (Pt o, long double r = 0): o(o), r(r) {}
    void read ()
    {
        o.read(), scanf("%lf", &r);
    }
    Pt pt(long double rad)
    {
        return Pt(o.x + cos(rad)*r, o.y + sin(rad)*r);
    }
    long double getArea (long double rad)
    {
        return rad * r * r / 2;
    }
//area of the circular sector cut by a chord with central angle alpha
    long double sector(long double alpha)
    {
        return r * r * 0.5 * (alpha - sin(alpha));
    }
};
int getLineCircleIntersection (Pt p, Pt q, Circle O, long double& t1, long double& t2, vector<Pt>& sol)
{
//    debug(p.x,p.y,q.x,q.y,O.o.x,O.o.y,O.r);
    Vector v = q - p;
    //sol.clear();
    long double a = v.x, b = p.x - O.o.x, c = v.y, d = p.y - O.o.y;
    long double e = a*a+c*c, f = 2*(a*b+c*d), g = b*b+d*d-O.r*O.r;
    long double delta = f*f - 4*e*g;
    if (dcmp(delta) < 0) return 0;
//    if (dcmp(delta) == 0)
//    {
//        t1 = t2 = -f / (2 * e);
//        sol.push_back(p + v * t1);
////        debug(1);
//        return 1;
//    }
    t1 = (-f - sqrt(delta)) / (2 * e);
    sol.push_back(p + v * t1);
    t2 = (-f + sqrt(delta)) / (2 * e);
    sol.push_back(p + v * t2);
    return 2;
}

void check( vector<PT>& fig)
{
    ll res = 0;
    for (unsigned i = 0; i < fig.size(); i++)
    {
        PT p = i ? fig[i - 1] : fig.back();
        PT q = fig[i];
        res += (p.x - q.x) * (p.y + q.y);
    }
    if(res<0)
        reverse(fig.begin(),fig.end());
}

int n,R;
vector<PT>v;
vector<pair<ld,int>>pq;



void maro(PT A,PT B)
{
    if(abs(A.y)>abs(B.y))
        swap(A,B);

    ld vx=B.x-A.x,vy=B.y-A.y;

    if(abs(A.y)>=R)
        return;

    vector<PT>sol;
    long double t1,t2;
    getLineCircleIntersection(PT(-1e6,0),PT(1e6,0),Circle(A,R),t1,t2,sol);


    ld min_x=1e6,max_x=-1e6;
    for(auto u:sol)
    {
        min_x=min(min_x,u.x);
        max_x=max(max_x,u.x);
    }

//    debug(min_x,max_x,vx,vy);


    ld low=0,high=1;
    int cnt=1000;
    while(cnt--)
    {
        ld mid=(low+high)/2;
        PT temp=A;
        temp.x+=vx*mid;
        temp.y+=vy*mid;

        vector<PT>sol;
        long double t1,t2;
        int ee=getLineCircleIntersection(PT(-1e6,0),PT(1e6,0),Circle(temp,R),t1,t2,sol);
        if(ee==0)
        {
            high=mid;
        }
        else
        {
            low=mid;
            for(auto u:sol)
            {
                min_x=min(min_x,u.x);
                max_x=max(max_x,u.x);
//                debug(u.x,u.y,temp.x,temp.y,R,cnt);
            }
        }
    }
    if(min_x<=max_x)
    {
        pq.push_back({min_x,2});
        pq.push_back({max_x,3});
    }
//    cout<<"x "<<A.x<<' '<<A.y<<' '<<B.x<<' '<<B.y<<endl;
//    debug(min_x,max_x);
}

void TEST_CASES()
{
    cin>>n>>R;
    v.resize(n);
    for(int i=0; i<n; i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    check(v);

//    for(auto u:v)
//        cout<<u.x<<' '<<u.y<<endl;
//    cout<<endl;

    for(int i=0; i<n; i++)
    {
        if(v[i].y==0&&v[(i+1)%n].y==0)
        {
            maro(v[i],v[(i+1)%n]);
            continue;
        }
        auto where=seg_seg_intersection_inside(v[i],v[(i+1)%n],PT(-1e6,0),PT(1e6,0));
        if(where.size()==0)
        {
            maro(v[i],v[(i+1)%n]);
            continue;
        }

        auto which=*where.begin();
        if(v[i].y<v[(i+1)%n].y)
        {
            pq.push_back({which.x,1});
            debug(i,which.x,0);
        }
        else
        {
            pq.push_back({which.x,0});
            debug(i,which.x,1);
        }
        maro(v[i],which);
        maro(which,v[(i+1)%n]);

    }
    cout<<fixed<<setprecision(10);
    sort(pq.begin(),pq.end());
    debug(pq);

    int hit=0;
    bool on=0;
    ld ans=0;
    for(int i=0;i+1<pq.size();i++)
    {
        long double gap=pq[i+1].first-pq[i].first;
        if(pq[i].second==0) on=1;
        else if(pq[i].second==1) on=0;
        else if(pq[i].second==2) hit++;
        else hit--;

        if(on&&hit==0)
            ans+=gap;
    }
    cout<<fixed<<setprecision(9)<<ans;


}


/*
*/

int32_t main()
{
#ifndef IFT
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    //freopen("input.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        TEST_CASES();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3836kb

input:

4 5
-5 -5
5 -5
5 5
-5 5

output:

0.000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

4 5
-10 -10
10 -10
10 10
-10 10

output:

10.000000007

result:

ok found '10.00000', expected '10.00000', error '0.00000'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 4004kb

input:

9 10
-100 -80
-90 130
-30 150
0 160
100 130
120 90
110 -60
80 -100
0 -120

output:

190.190476189

result:

wrong answer 1st numbers differ - expected: '190.15695', found: '190.19048', error = '0.00018'