QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#522216#6599. The Grand TournamentFLtheLeathermanWA 1ms3996kbC++204.1kb2024-08-16 19:44:072024-08-16 19:44:07

Judging History

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

  • [2024-08-16 19:44:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3996kb
  • [2024-08-16 19:44:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define double long double
const double esp = 1e-8;
typedef pair<double, double> P;
#define CP const P &
#define CL const Line& 
#define x first
#define y second

const int N =30;
struct Line
{
    P d, v;
    double s;
} line[N];

Line norm(Line a){
    a.v={a.v.y,-a.v.x};
    a.s=atan2(a.v.y,a.v.x);
    return a;
}
P operator-(CP a, CP b)
{
    return (P){a.x - b.x, a.y - b.y};
}

int sign(double a)
{
    if (fabs(a) < esp)
        return 0;
    if (a < 0)
        return -1;
    return 1;
}
double cross(CP a, CP b)
{
    return a.x * b.y - a.y * b.x;
}

P line_intersection(CL a,CL b)
{
    double t = cross(b.d - a.d, b.v) / cross(a.v, b.v);
    return (P){a.d.x + t * a.v.x, a.d.y + t * a.v.y};
}

bool on_right(CP d,CL line){
    return sign(cross(d-line.d,line.v))>=0;
}
void pr(CP d){
    cout<<d.x<<" "<<d.y<<endl;
}

bool cmp(CL a,CL b){
    if(sign(a.s-b.s)!=0)return a.s<b.s;
    return !on_right(a.d,b);
}

P ans[N];
int q[N];
int cntd=0;
int n,m,cnt=0;
void half_plane_intersection(int n){
    memset(q,0,sizeof(q));
    memset(ans,0,sizeof(ans));
    cntd=0;
    for(int i=1;i<=n;++i)line[i].s=atan2(line[i].v.y,line[i].v.x);
    sort(line+1,line+1+n,cmp);
    int hh=1,tt=0;
    for(int i=1;i<=n;++i){
        if(i&&sign(line[i].s-line[i-1].s)==0)continue;
        while(tt>=hh+1&&on_right(line_intersection(line[q[tt]],line[q[tt-1]]),line[i] ))tt--;
        while(tt>=hh+1&&on_right(line_intersection(line[q[hh]],line[q[hh+1]]),line[i] ))hh++;
        q[++tt]=i;
    }
    while(tt>=hh+1&&on_right(line_intersection(line[q[tt]],line[q[tt-1]]),line[q[hh]] ))tt--;
    q[++tt]=q[hh];
    for(int i=hh;i<tt;++i){
        ans[++cntd]=line_intersection(line[q[i]],line[q[i+1]]);
    }
}
double area(P a,P b){
    return fabs(a.x*b.y-a.y*b.x);
}
double area(P d[],int n){
    double res=0;
    d[n+1]=d[1];
    for(int i=1;i<n;++i){
        res+=cross(d[i]-d[1],d[i+1]-d[1]);
    }
    return res/2;
}
double kk(P a){
    return atan2(a.y,a.x);
}
void pr(double x){
    if(x<0)x*=-1;
    printf("%.10Lf",x);
    cout<<endl;
}
void solve()
{
    P x1, x2, x3, x4, x5, x6;
    cin >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> x4.x >> x4.y >> x5.x >> x5.y >> x6.x >> x6.y;
    if(x3>x4)swap(x3,x4);
    if(x5>x6)swap(x5,x6);
    double ans=0;
    P a=x1,b={x2.x,x1.y},c=x2,d={x1.x,x2.y};
    if(sign(area(x4-x3,x5-x3))==0&&sign(area(x4-x3,x6-x3))==0){
        P aa=max(x3,x5),bb=min(x4,x6);
        if(aa<bb){

            line[1]={a,b-a,0};
            line[2]={b,c-b,0};
            line[3]={c,d-c,0};
            line[4]={d,a-d,0};  
            line[5]=norm((Line){aa,bb-aa,0});
            line[6]=norm((Line){bb,aa-bb,0});
        }
        half_plane_intersection(6);
        ans+=area(::ans,cntd);
    }
    

    if(x3==x5){
        line[1]={a,b-a,0};
        line[2]={b,c-b,0};
        line[3]={c,d-c,0};
        line[4]={d,a-d,0};  
        line[5]=norm((Line){x3,x3-x4,0});
        line[6]=norm((Line){x5,x5-x6,0});
        half_plane_intersection(6);
        ans+=area(::ans,cntd);
    }

    if(x4==x5){
        line[1]={a,b-a,0};
        line[2]={b,c-b,0};
        line[3]={c,d-c,0};
        line[4]={d,a-d,0};  
        line[5]=norm((Line){x4,x4-x3,0});
        line[6]=norm((Line){x5,x5-x6,0});
        half_plane_intersection(6);
        ans+=area(::ans,cntd);
    }
    if(x3==x6){
        line[1]={a,b-a,0};
        line[2]={b,c-b,0};
        line[3]={c,d-c,0};
        line[4]={d,a-d,0};  
        line[5]=norm((Line){x3,x3-x4,0});
        line[6]=norm((Line){x6,x6-x5,0});
        half_plane_intersection(6);
        ans+=area(::ans,cntd);
    }
    if(x4==x6){
        line[1]={a,b-a,0};
        line[2]={b,c-b,0};
        line[3]={c,d-c,0};
        line[4]={d,a-d,0};  
        line[5]=norm((Line){x4,x4-x3,0});
        line[6]=norm((Line){x6,x6-x5,0});
        half_plane_intersection(6);
        ans+=area(::ans,cntd);
    }
    if(isnan(ans))pr(0);
    else pr(ans);
}

signed main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
0 0 3 3
1 1 1 2
2 1 2 2
0 0 3 3
1 1 1 2
1 2 2 2

output:

0.0000000000
1.0000000000

result:

ok 2 numbers

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3996kb

input:

10
0 0 7 6
2 4 4 4
3 2 5 2
0 0 7 6
2 4 4 4
4 4 5 2
0 0 2 4
1 1 1 2
1 2 1 3
0 0 2 3
1 1 1 2
1 1 1 2
0 0 3 3
1 1 2 2
1 2 2 1
0 0 2 4
1 1 1 2
1 2 1 3
0 0 6 6
1 1 5 5
1 5 3 3
0 0 2 3
1 1 1 2
1 1 1 2
0 0 2 5
1 1 1 3
1 2 1 4
0 0 2 4
1 1 1 3
1 1 1 2

output:

0.0000000000
3.7500000000
3.7500000000
6.0000000000
0.0000000000
2.0000000000
0.0000000000
6.0000000000
2.0000000000
4.0000000000

result:

wrong answer 3rd numbers differ - expected: '0.0000000', found: '3.7500000', error = '3.7500000'