QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279414 | #7783. Military Maneuver | ucup-team1447# | WA | 3010ms | 14112kb | C++14 | 5.6kb | 2023-12-08 17:59:48 | 2023-12-08 17:59:48 |
Judging History
answer
/* Never Island */
/*deco loves Chino*/
#include <bits/stdc++.h>
#define double long double
double sh;
using namespace std;
const double eps=1e-13;
int n,m;
double x[1234567],y[1234567];
inline int read()
{
int num=0,f=1;char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>47&&c<58)num=num*10+(c^48),c=getchar();
return num*f;
}
double xl=read(),yl=read(),xr=read(),yr=read();
namespace qwq{
#define QAQ int
#define TAT long long
#define OwO bool
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))
using namespace std;
const int N=40005;
const double eps=1e-9;
struct Point{
double x,y;
friend Point operator - (Point a,Point b){
Point t;
t.x=a.x-b.x;t.y=a.y-b.y;
return t;
}
friend Point operator + (Point a,Point b){
Point t;
t.x=a.x+b.x;t.y=a.y+b.y;
return t;
}
friend double operator * (Point a,Point b){
return a.x*b.x+a.y*b.y;
}
friend double operator ^ (Point a,Point b){
return a.x*b.y-b.x*a.y;
}
friend Point operator * (double k,Point b){
Point t;
t.x=k*b.x;t.y=k*b.y;
return t;
}
}b[N];
int sign(double x){
return fabs(x)<=eps ? 0 : (x>0 ? 1 : -1);
}
struct Line{
Point p,v;
Line(Point x,Point y):p(x),v(y){}
Line(){}
double poa;
friend OwO operator < (Line x,Line y){
return sign(x.poa-y.poa)==0 ? sign((x.v-x.p) ^ (y.v-x.p)) >0 : sign(x.poa-y.poa)<0;
//因为我是向量左侧求交,所以极角相同时靠左的更优,把优的放在后面,方便之后的操作 ,可以画图体会一下
}
}a[N],q[N];
int js,cnt,head,tail;
double ans;
Point inter(Line a,Line b){//求交点
Point p1=a.p,p2=b.p,v1=a.v,v2=b.v;
v1=v1-p1;v2=v2-p2;
Point u=p2-p1;
// if(fabs(u^v1)<eps)return p2;
// assert(fabs((v1^v2))>eps);
Point p=p2+((u^v1)/(v1^v2))*v2;
return p;
}
OwO pd(Line i,Line j,Line k){
// assert(fabs(i.v-i.p^j.v-j.p)>eps);
Point p=inter(i,j);
return sign((k.v-k.p) ^ (p-k.p))<eps;
}
void Half_Plane(){
sort(a+1,a+js+1);//排序
cnt=0;
F(i,1,js) {
if(sign(a[i].poa-a[i-1].poa)!=0) cnt++;
a[cnt]=a[i];//因为排过序,即使极角相同,后面的也比前面的优
}
head=1;tail=0;
q[++tail]=a[1];q[++tail]=a[2];
F(i,3,cnt){
while(head<tail&&pd(q[tail-1],q[tail],a[i])) tail--;//维护双端队列
while(head<tail&&pd(q[head+1],q[head],a[i])) head++;
q[++tail]=a[i];
}
while(head<tail&&pd(q[tail-1],q[tail],q[head])) tail--;
while(head<tail&&pd(q[head+1],q[head],q[tail])) head++;
q[tail+1]=q[head];
js=0;
F(i,head,tail) b[++js]=inter(q[i],q[i+1]);
}
int main(int v,int tp)
{
// int n;
// cin>>n;
int &sum=js;
sum=0;
// for(int i=1;i<=n;i++)
// {
// cin>>m;
// for(int j=1;j<=m;j++)
// {
// scanf("%lf%lf",&Q[j].x,&Q[j].y);
// }
// for(int j=1;j<=m;j++)
// {
// ++sum;
// int to=j+1;
// if(j==m)
// {
// to=1;
// }
// P[sum]=line(Q[j],Q[to]-Q[j]);
// }
// }
a[++sum]=Line({xl,yl},{1,0});
a[++sum]=Line({xr,yl},{0,1});
a[++sum]=Line({xr,yr},{-1,0});
a[++sum]=Line({xl,yr},{0,-1});
for(int i=1;i<v;i++)
if(x[i]==x[v]&&y[i]==y[v])return 0;
for(int i=1;i<=n;i++)
{
if(x[i]==x[v]&&y[i]==y[v])continue;
double p=(x[i]+x[v])/2,q=(y[i]+y[v])/2;
double r=(x[i]-x[v]),s=(y[i]-y[v]);
std::swap(r,s);
if(tp)s=-s;else r=-r;
a[++sum]=Line({p,q},{r,s});
}
F(i,1,js) a[i].poa=atan2(a[i].v.y-a[i].p.y,a[i].v.x-a[i].p.x);
F(i,1,js)a[i].v.x*=1e0,a[i].v.y*=1e0;
F(i,1,js)a[i].v.x+=a[i].p.x,a[i].v.y+=a[i].p.y;
Half_Plane();
b[js+1]=b[1];
double tmp=0;
if(js>2)
{
// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf %.3lf %.3lf \n",q[i].p.x,q[i].p.y,q[i].v.x,q[i].v.y);
// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf\n",b[i].x,b[i].y);
// puts("");
double d=x[v];
for(int i=head;i<=tail;i++)
{
auto [l,x]=b[i];
auto [r,y]=b[i==tail?head:i+1];
if(fabs(r-l)<eps)continue;
double k=(y-x)/(r-l),b=x-l*k;
double f4=k/4;
double f3=(b-2*d*k)/3;
double f2=(d*k-2*b)*d/2;
double f1=d*d*b;
auto calc=[&](double t)
{
return t*t*t*t*f4+t*t*t*f3+t*t*f2+t*f1;
};
double v=calc(r)-calc(l);
if(tp)v=-v;
sh+=v;
// printf("(%d %.3lf %.3lf)ans+=%.12lf\n",i,k,b,v);
}
// puts("xx");
}
if(js>2)
{
// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf %.3lf %.3lf \n",q[i].p.x,q[i].p.y,q[i].v.x,q[i].v.y);
// for(int i=head;i<=tail;i++)printf("%.3lf %.3lf\n",b[i].x,b[i].y);
// puts("");
// puts("");
double d=y[v];
for(int i=head;i<=tail;i++)
{
auto [x,l]=b[i];
auto [y,r]=b[i==tail?head:i+1];
if(fabs(r-l)<eps)continue;
double k=(y-x)/(r-l),b=x-l*k;
double f4=k/4;
double f3=(b-2*d*k)/3;
double f2=(d*k-2*b)*d/2;
double f1=d*d*b;
auto calc=[&](double t)
{
return t*t*t*t*f4+t*t*t*f3+t*t*f2+t*f1;
};
// printf("%.3lfx^4+%.3lfx^3+%.3lfx^2+%.3lfx\n",f4,f3,f2,f1);
double v=calc(r)-calc(l);
if(!tp)v=-v;
// printf("ansy+=%.12lf\n",v);
sh+=v;
}
// puts("yy");
}
// F(i,1,js) tmp+=(b[i]^b[i+1]);
// printf("%.3lf\n",tmp);
// sort(a+1,P+sum+1);//极角排序
// work();
// solve();
// puts("");
return 0;
}
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
for(int i=1;i<=n;i++)qwq::main(i,0);
for(int i=1;i<=n;i++)qwq::main(i,1);
// printf("%.12l?f\n",sh);
sh*=acosl(-1);
printf("%.12Lf\n",sh/(xr-xl)/(yr-yl));
// printf("%.12lf\n",8.377580409572781970/acos(-1));
// printf("%.12lf\n",37.699111843077518863/acos(-1));
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 12052kb
input:
0 0 2 2 2 3 1 1 3
output:
8.377580409573
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11968kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843078
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 3010ms
memory: 14112kb
input:
-2911 2151 336 5941 2000 -83 79 -94 47 48 -29 -47 64 84 75 -44 -86 -58 -11 -31 58 20 53 80 -19 -82 74 -60 -26 8 -68 -42 -61 -14 12 -58 -18 92 10 35 -26 71 64 76 89 -80 6 70 4 -96 -99 95 -80 -3 -22 71 -89 -75 17 -35 -82 -59 95 60 48 -74 50 -82 90 -26 5 -75 -31 -45 85 85 14 -70 -57 59 46 55 13 -23 60 ...
output:
-nan
result:
wrong output format Expected double, but "-nan" found