QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390391 | #3737. 三角形和矩形 | ROCKET | AC ✓ | 6ms | 3960kb | C++17 | 3.8kb | 2024-04-15 14:57:04 | 2024-04-15 14:57:04 |
Judging History
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[0]=Point(x3,y3);
b[1]=Point(x3,y4);
b[2]=Point(x4,y4);
b[3]=Point(x4,y3);
printf("%.8f\n",fabs(SPIA(a,b,3,4)));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3912kb
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: 0ms
memory: 3920kb
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: 3912kb
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: 6ms
memory: 3960kb
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: 3928kb
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: 3904kb
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: 3920kb
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.41988130 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