QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293403 | #7783. Military Maneuver | ucup-team191# | WA | 2077ms | 4468kb | C++23 | 6.0kb | 2023-12-29 06:46:27 | 2023-12-29 06:46:27 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using ld=long double;
#define double ld
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
#define rep(i,a,b) for (int i=a;i<(b);++i)
#define sz(x) (int)(x).size()
const int N=2010,MOD=1e9+7;
const double eps=1e-8;
const char en='\n';
const ll LLINF=1ll<<60;
template<class T> int sgn(T x) {return (x>0)-(x<0);}
template<class T>
struct Point
{
typedef Point P;
T x,y;
explicit Point(T x=0,T y=0) : x(x),y(y) {}
bool operator<(P p) const {return tie(x,y)<tie(p.x,p.y);}
bool operator==(P p) const {return tie(x,y)==tie(p.x,p.y);}
P operator+(P p) const {return P(x+p.x,y+p.y);}
P operator-(P p) const {return P(x-p.x,y-p.y);}
P operator*(T d) const {return P(x*d,y*d);}
P operator/(T d) const {return P(x/d,y/d);}
T dot(P p) const {return x*p.x+y*p.y;}
T cross(P p) const {return x*p.y-y*p.x;}
T cross(P a,P b) const {return (a-*this).cross(b-*this);}
T dist2() const {return x*x+y*y;}
double dist() const {return sqrt((double)dist2());}
double angle() const {return atan2(y,x);}
P unit() const {return *this/dist();}
P perp() const {return P(-y,x);}
P normal() const {return perp().unit();}
P rotate(double a) const {return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a));}
friend ostream& operator<<(ostream& os,P p) {return os<<"("<<p.x<<","<<p.y<<")";}
};
template<class P>
int sideOf(P s,P e,P p) {return sgn(s.cross(e,p));}
template<class P>
int sideOf(const P&s,const P&e,const P&p,double eps)
{
auto a=(e-s).cross(p-s);
double l=(e-s).dist()*eps;
return (a>l)-(a<-l);
}
template<class P>
pair<int,P> lineInter(P s1,P e1,P s2,P e2)
{
auto d=(e1-s1).cross(e2-s2);
if (d==0)
{
return {-(s1.cross(e1,s2)==0),P(0,0)};
}
auto p=s2.cross(e1,e2),q=s2.cross(e2,s1);
return {1,(s1*p+e1*q)/d};
}
using P=Point<double>;
struct Line
{
P x;
P y;
double ang;
explicit Line(P x=P(0,0),P y=P(0,0)) : x(x),y(y) {ang=(y-x).angle();}
};
#define sp(a) a.x, a.y
int angDiff(Line a,Line b)
{
return sgn(a.ang-b.ang);
}
bool cmp(Line a,Line b)
{
int s=angDiff(a,b);
return (s?s:sideOf(sp(a),b.x))<0;
}
vector<P> halfPlaneIntersection(vector<Line> vs)
{
const double EPS=sqrt(2)*1e-8;
sort(all(vs),cmp);
vector<Line> deq(sz(vs)+5);
vector<P> ans(sz(vs)+5);
deq[0]=vs[0];
int ah=0,at=0,n=sz(vs);
rep(i,1,n+1)
{
if (i==n) vs.pb(deq[ah]);
if (angDiff(vs[i],vs[i-1])==0) continue;
while (ah<at && sideOf(sp(vs[i]),ans[at-1],EPS)<0) at--;
while (i!=n && ah<at && sideOf(sp(vs[i]),ans[ah],EPS)<0) ah++;
auto res=lineInter(sp(vs[i]),sp(deq[at]));
if (res.first!=1) continue;
ans[at++]=res.y;
deq[at]=vs[i];
}
if (at-ah<=2) return {};
return {ans.begin()+ah,ans.begin()+at};
}
vector<P> improve(vector<P> v)
{
if (v.size()==1) return v;
sort(all(v));
vector<P> h(sz(v)+1);
int s=0,t=0;
for (int it=2;it--;s=--it,reverse(all(v)))
{
for (P p: v)
{
while (t>=s+2 && h[t-2].cross(h[t-1],p)<=0) t--;
h[t++]=p;
}
}
return {h.begin(),h.begin()+t-(t==2 && h[0]==h[1])};
}
template<class T>
void prVec(T x)
{
cout<<sz(x)<<endl;
for (auto u: x) cout<<u<<' ';
cout<<endl;
}
double getInt1(double x,double a1,double b1,double a2,double b2)
{
return pow(x,3)/3*((a1-a2)*x+(b1-b2))-(a1-a2)/12*pow(x,4)+1/(12*a1)*pow(a1*x+b1,4)-1/(12*a2)*pow(a2*x+b2,4);
}
double getInt2(double lo,double hi,double a1,double b1,double a2,double b2)
{
return getInt1(hi,a1,b1,a2,b2)-getInt1(lo,a1,b1,a2,b2);
}
pair<double,double> getPrav(P a,P b)
{
double nag=(b.y-a.y)/(b.x-a.x);
return {nag,a.y-a.x*nag};
}
double eval(pair<double,double> p,double x)
{
return p.x*x+p.y;
}
double getInt(P a,P b,P c)
{
if (abs(a.cross(b,c))<eps) return 0;
if (b<a) swap(a,b);
if (c<a) swap(a,c);
if (c<b) swap(b,c);
//a<=b<=c
if (a.x==b.x)
{
if (b.x==c.x) return 0;
auto p1=getPrav(a,c),p2=getPrav(b,c); //p2 gornji, p1 donji
return getInt2(a.x,c.x,p2.x,p2.y,p1.x,p1.y);
}
if (b.x==c.x)
{
auto p1=getPrav(a,b),p2=getPrav(a,c);
return getInt2(a.x,c.x,p2.x,p2.y,p1.x,p1.y);
}
auto p1=getPrav(a,b),p2=getPrav(a,c),p3=getPrav(b,c);
double an=0;
if (eval(p1,a.x+eps)<eval(p2,a.x+eps)) //p1 ispod p2
{
an+=getInt2(a.x,b.x,p2.x,p2.y,p1.x,p1.y);
}
else
{
an+=getInt2(a.x,b.x,p1.x,p1.y,p2.x,p2.y);
}
if (eval(p2,b.x+eps)<eval(p3,b.x+eps)) //p2 ispod p3
{
an+=getInt2(b.x,c.x,p3.x,p3.y,p2.x,p2.y);
}
else
{
an+=getInt2(b.x,c.x,p2.x,p2.y,p3.x,p3.y);
}
return an;
}
int n,xl,yl,xr,yr;
P po[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
const double ROT=0.01;
cin>>xl>>yl>>xr>>yr>>n;
vector<P> prav;
prav.pb(P(xl,yl).rotate(ROT));
prav.pb(P(xr,yl).rotate(ROT));
prav.pb(P(xr,yr).rotate(ROT));
prav.pb(P(xl,yr).rotate(ROT));
vector<Line> pravl;
for (int i=0;i<4;++i) pravl.pb(Line(prav[i],prav[(i+1)%4]));
for (int i=0;i<n;++i) cin>>po[i].x>>po[i].y,po[i]=po[i].rotate(ROT);
double an=0;
for (int i=0;i<n;++i)
{
vector<Line> v1=pravl,v2=pravl;
for (int j=0;j<n;++j) if (i!=j)
{
P z=(po[i]+po[j])/2,pro=(po[j]-po[i]).perp();
P x=z-pro,y=z+pro;
v1.pb(Line(x,y));
v2.pb(Line(y,x));
}
auto r1=halfPlaneIntersection(v1),r2=halfPlaneIntersection(v2);
//cout<<i<<endl;
//r1=improve(r1);
//r2=improve(r2);
//prVec(r1);
//prVec(r2);
P pp=po[i];
if (r1.size())
{
for (int i=2;i<sz(r1);++i)
{
an+=getInt(r1[0]-pp,r1[i-1]-pp,r1[i]-pp);
//cout<<r1[0]-pp<<' '<<r1[i-1]-pp<<' '<<r1[i]-pp<<' '<<getInt(r1[0]-pp,r1[i-1]-pp,r1[i]-pp)<<endl;
}
}
if (r2.size())
{
for (int i=2;i<sz(r2);++i)
{
an-=getInt(r2[0]-pp,r2[i-1]-pp,r2[i]-pp);
//cout<<r2[0]-pp<<' '<<r2[i-1]-pp<<' '<<r2[i]-pp<<' '<<getInt(r2[0]-pp,r2[i-1]-pp,r2[i]-pp)<<endl;
}
}
}
const double pi=acos(-1);
cout<<fixed<<setprecision(15);
cout<<-an*pi/(yr-yl)/(xr-xl)<<endl;
//cout<<an<<' '<<pi<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3908kb
input:
0 0 2 2 2 3 1 1 3
output:
8.377580409572782
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843077518
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 2077ms
memory: 4468kb
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:
30574955655717180413917015504254623577097576185377972956764957062281201838428008742912.000000000000000
result:
wrong answer 1st numbers differ - expected: '6657168.1428534', found: '30574955655717179918527995495361617350091173961392259328682428298098182498149170413568.0000000', error = '4592787052936323157396172947389882034509508853766494470370200146092516672798720.0000000'