QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293403#7783. Military Maneuverucup-team191#WA 2077ms4468kbC++236.0kb2023-12-29 06:46:272023-12-29 06:46:27

Judging History

你现在查看的是最新测评结果

  • [2023-12-29 06:46:27]
  • 评测
  • 测评结果:WA
  • 用时:2077ms
  • 内存:4468kb
  • [2023-12-29 06:46:27]
  • 提交

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'