QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390397#3737. 三角形和矩形ROCKETAC ✓6ms3952kbC++173.9kb2024-04-15 15:00:502024-04-15 15:00:52

Judging History

This is the latest submission verdict.

  • [2024-04-15 15:00:52]
  • Judged
  • Verdict: AC
  • Time: 6ms
  • Memory: 3952kb
  • [2024-04-15 15:00:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for(int i=a;i<n;i++)
#define mem(a,n) memset(a,n,sizeof(a))
#define pb push_back
#define IO ios::sync_with_stdio(false);
typedef long long ll;
typedef double DBL;
const int N=5e2+5;
const int maxn=510;
const double eps=1e-4;
const int MOD=1e9+7;
const int dir[4][2]= {-1,0,1,0,0,-1,0,1}; ///上下左右
const int INF=0x3f3f3f3f;

int dcmp(double x)
{
    if(x>eps) return 1;
    return x<-eps ? -1 : 0;
}
inline double Sqr(double x)
{
    return x*x;
}
struct Point
{
    double x,y;
    Point()
    {
        x=y=0;
    }
    Point(double x,double y):x(x),y(y) {};
    friend Point operator + (const Point &a,const Point &b)
    {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b)
    {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const Point &a,const Point &b)
    {
        return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
    }
    friend Point operator * (const Point &a,const double &b)
    {
        return Point(a.x*b,a.y*b);
    }
    friend Point operator * (const double &a,const Point &b)
    {
        return Point(a*b.x,a*b.y);
    }
    friend Point operator / (const Point &a,const double &b)
    {
        return Point(a.x/b,a.y/b);
    }
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
    inline double dot(const Point &b)const
    {
        return x*b.x+y*b.y;
    }
    inline double cross(const Point &b,const Point &c)const
    {
        return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);
    }

};

Point LineCross(const Point &a,const Point &b,const Point &c,const Point &d)
{
    double u=a.cross(b,c),v=b.cross(a,d);
    return Point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
}
double PolygonArea(Point p[],int n)
{
    if(n<3) return 0.0;
    double s=p[0].y*(p[n-1].x-p[1].x);
    p[n]=p[0];
    for(int i=1; i<n; i++)
    {
        s+=p[i].y*(p[i-1].x-p[i+1].x);
    }
    return fabs(s*0.5);
}
double CPIA(Point a[],Point b[],int na,int nb)
{
    Point p[maxn],temp[maxn];
    int i,j,tn,sflag,eflag;
    a[na]=a[0],b[nb]=b[0];
    memcpy(p,b,sizeof(Point)*(nb+1));
    for(i=0; i<na&&nb>2; ++i)
    {
        sflag=dcmp(a[i].cross(a[i+1],p[0]));
        for(j=tn=0; j<nb; ++j,sflag=eflag)
        {
            if(sflag>=0) temp[tn++]=p[j];
            eflag=dcmp(a[i].cross(a[i+1],p[j+1]));
            if((sflag^eflag)==-2)
                temp[tn++]=LineCross(a[i],a[i+1],p[j],p[j+1]);
        }
        memcpy(p,temp,sizeof(Point)*tn);
        nb=tn,p[nb]=p[0];
    }
    if(nb<3) return 0.0;
    return PolygonArea(p,nb);
}
double SPIA(Point a[],Point b[],int na,int nb)
{
    int i,j;
    Point t1[4],t2[4];
    double res=0.0,if_clock_t1,if_clock_t2;
    a[na]=t1[0]=a[0];
    b[nb]=t2[0]=b[0];
    for(i=2; i<na; i++)
    {
        t1[1]=a[i-1],t1[2]=a[i];
        if_clock_t1=dcmp(t1[0].cross(t1[1],t1[2]));
        if(if_clock_t1<0) swap(t1[1],t1[2]);
        for(j=2; j<nb; j++)
        {
            t2[1]=b[j-1],t2[2]=b[j];
            if_clock_t2=dcmp(t2[0].cross(t2[1],t2[2]));
            if(if_clock_t2<0) swap(t2[1],t2[2]);
            res+=CPIA(t1,t2,3,3)*if_clock_t1*if_clock_t2;
        }
    }
    return res;//面积交
    //return PolygonArea(a,na)+PolygonArea(b,nb)-res;//面积并
}
Point a[4],b[5];

int main()
{
    int x1,x2,x3,x4,y1,y2,y3,y4;
    while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2))
    {
        scanf("%d%d%d%d",&x3,&y3,&x4,&y4);
        a[0]=Point(x1,y1); //无顺序要求
        a[1]=Point(x2,y1);
        a[2]=Point(x1,y2);

        b[1]=Point(x3,y3);
        b[0]=Point(x3,y4);
        b[3]=Point(x4,y4);
        b[2]=Point(x4,y3);
        printf("%.8f\n",fabs(SPIA(a,b,3,4)));
    }
    return 0;
}


详细

Test #1:

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

input:

0 0 1 1
0 0 1 1
0 1 1 0
0 0 1 1
1 0 0 1
0 0 1 1
1 1 0 0
0 0 1 1

output:

0.50000000
0.50000000
0.50000000
0.50000000

result:

ok 4 numbers

Test #2:

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

input:

0 0 1 1
0 0 1 1
0 0 1 1
0 0 1 2
0 0 1 1
0 1 1 2
0 0 1 1
0 0 2 1
0 0 1 1
0 0 2 2
0 0 1 1
0 1 2 2
0 0 1 1
1 0 2 1
0 0 1 1
1 0 2 2
0 0 1 1
1 1 2 2
0 0 1 2
0 0 1 1
0 0 1 2
0 0 1 2
0 0 1 2
0 1 1 2
0 0 1 2
0 0 2 1
0 0 1 2
0 0 2 2
0 0 1 2
0 1 2 2
0 0 1 2
1 0 2 1
0 0 1 2
1 0 2 2
0 0 1 2
1 1 2 2
0 1 1 0
0 0 ...

output:

0.50000000
0.50000000
0.00000000
0.50000000
0.50000000
0.00000000
0.00000000
0.00000000
0.00000000
0.75000000
1.00000000
0.25000000
0.75000000
1.00000000
0.25000000
0.00000000
0.00000000
0.00000000
0.50000000
0.50000000
0.00000000
0.50000000
0.50000000
0.00000000
0.00000000
0.00000000
0.00000000
0.0...

result:

ok 324 numbers

Test #3:

score: 0
Accepted
time: 6ms
memory: 3952kb

input:

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

output:

0.50000000
0.50000000
0.50000000
0.00000000
0.00000000
0.00000000
0.50000000
0.50000000
0.50000000
0.00000000
0.00000000
0.00000000
0.50000000
0.50000000
0.50000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.0...

result:

ok 5184 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 3928kb

input:

3 0 0 2
3 3 10 7
2 2 4 3
0 2 8 5
8 0 4 8
3 1 5 5
6 0 5 7
4 6 5 7
1 0 2 9
3 5 10 8
10 2 6 10
5 1 6 4
8 4 2 3
7 6 9 10
10 5 6 0
0 0 7 5
0 3 7 0
0 6 4 8
1 10 9 8
0 3 2 4
10 5 8 9
3 8 9 10
7 6 1 7
2 8 6 9
2 1 7 5
3 5 10 9
0 3 2 10
0 0 7 8
3 5 5 8
3 1 4 9
1 2 6 0
1 7 7 9
1 0 0 3
3 2 5 6
8 5 9 1
3 1 9 8
1...

output:

0.00000000
1.00000000
0.25000000
0.00000000
0.00000000
0.00000000
0.00000000
0.62500000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
6.42857143
2.25000000
0.00000000
0.00000000
2.00000000
1.87500000
6.00000000
2.50000000
3.37500000
0.00000000
15.75000000
1.00000000
0.00000000
0.00000000
0....

result:

ok 5000 numbers

Test #5:

score: 0
Accepted
time: 6ms
memory: 3924kb

input:

14 2 87 82
2 28 83 94
7 39 97 47
29 29 74 91
95 62 17 90
42 30 81 67
96 22 28 44
42 68 73 77
94 14 33 41
21 54 30 71
49 97 87 56
37 30 94 79
43 24 74 72
7 7 20 74
53 49 12 38
12 21 43 93
46 56 70 17
55 75 70 79
76 19 7 29
16 1 32 64
66 70 72 48
12 48 19 87
7 37 91 47
69 18 78 39
56 94 10 57
21 11 44...

output:

1330.42500000
182.00000000
195.00000000
0.00000000
0.00000000
245.14634146
0.00000000
128.91463415
0.00000000
39.42028986
0.00000000
17.14047619
166.12925969
0.00000000
0.00000000
44.00000000
0.00000000
125.00000000
644.64285714
505.04347826
5.44680851
0.00000000
0.00000000
0.00000000
0.00000000
0.0...

result:

ok 5000 numbers

Test #6:

score: 0
Accepted
time: 6ms
memory: 3908kb

input:

938 400 480 63
107 548 331 685
192 885 842 79
239 314 794 320
107 129 935 2
146 290 519 804
258 369 105 289
12 236 476 661
828 488 598 637
532 280 755 765
723 670 414 51
104 150 954 319
152 746 9 848
294 342 384 675
384 729 646 660
661 153 755 484
253 402 784 25
409 560 680 945
999 635 985 671
559 1...

output:

0.00000000
869.61290323
0.00000000
6120.00000000
7984.13260870
15480.70032310
0.00000000
0.00000000
0.00000000
0.00000000
33022.57399103
18287.88732394
11025.00000000
15125.00000000
2784.75000000
0.00000000
0.00000000
0.00000000
32973.26032601
0.00000000
64.09090909
6769.38906752
0.00000000
0.000000...

result:

ok 5000 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 3908kb

input:

2936 9085 2651 3900
6212 5326 9184 7331
1927 8406 4368 6471
691 2255 4724 5180
6652 6314 3973 1902
2894 4978 9758 5661
6311 1630 7262 8836
3735 9261 6091 9749
8338 7323 571 1074
2275 5452 4487 8549
2955 8550 8942 1842
8522 925 9674 9591
3004 6522 4133 753
6771 1311 8623 5719
8341 2286 1724 7067
4461...

output:

0.00000000
0.00000000
1417315.17395739
0.00000000
3983266.25757957
98821.71371305
0.00000000
0.00000000
0.00000000
60061.19328152
655933.41988131
0.00000000
0.00000000
620460.61593646
0.00000000
5139908.77819455
2519028.00000000
0.00000000
2343853.52596538
0.00000000
0.00000000
2454149.14995666
6555...

result:

ok 5000 numbers