QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#522216 | #6599. The Grand Tournament | FLtheLeatherman | WA | 1ms | 3996kb | C++20 | 4.1kb | 2024-08-16 19:44:07 | 2024-08-16 19:44:07 |
Judging History
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();
}
}
詳細信息
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'