QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729620#9576. Ordainer of Inexorable Judgmentucup-team159#WA 1ms4376kbC++2311.6kb2024-11-09 17:30:072024-11-09 17:30:09

Judging History

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

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-09 17:30:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4376kb
  • [2024-11-09 17:30:07]
  • 提交

answer

#line 1 "M.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

#line 2 "/home/sigma/comp/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 5 "M.cpp"

using D = double;
using P = complex<D>;
using L = pair<P,P>;
using Pol = vector<P>;
struct C{P p;D r;};
D inf=1e50,eps=1e-10,PI=acos(0.0)*2;
bool eq(D a, D b) { return abs(a-b)<eps;}
bool eq(P a, P b) { return abs(a-b)<eps;}
int sig(D a) { return eq(a,0) ? 0 : (a>0 ? 1 : -1);}
int large(D a,D b){return eq(a,b)?0:(a>b?1:-1);}
bool compxy (const P& l, const P& r){
	return eq(l.real(),r.real()) ? l.imag()<r.imag() : l.real() < r.real();
}
bool compyx (const P& l, const P& r){
	return eq(l.imag(),r.imag()) ? l.real()<r.real() : l.imag() < r.imag();
}
inline D dot(P a, P b) { return real(conj(a)*b);}
inline D cro(P a, P b) { return imag(conj(a)*b);}
//enum ENCCW{CCW(left)=1, CW(right)=-1, FRONT=-2, BACK=2, ON=0};
//ON優先(including endpoint)
inline int ccw (P a, P b, P c){
	if(sig(cro(b-a,c-a))==1) return 1;
	if(sig(cro(b-a,c-a))==-1) return -1;
	if(eq(abs(a-c)+abs(c-b),abs(a-b))) return 0;
	if(eq(abs(a-b)+abs(b-c),abs(a-c))) return -2;
	if(eq(abs(c-a)+abs(a-b),abs(c-b))) return 2;
	assert(false);
}
inline int ccw(L a,P p){return ccw(a.fs,a.sc,p);}
inline P proj(P a, P b){		//ベクトルaのbへの射影
	return (dot(a,b)/norm(b))*b;
}
inline D verlen(L l,P p){	//垂線の長さ(符号付き ccw(左)が正)
	return cro(l.sc-l.fs,p-l.fs)/abs(l.sc-l.fs);
}
inline P perp(L l, P p){		//垂線の足
	D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc);
	return l.fs+t*(l.fs-l.sc);
}
inline P refl(L l, P p){
	return p+2.0*(perp(l,p)-p);
}
inline bool ispal(L a, L b){
	return sig(cro(a.fs-a.sc,b.fs-b.sc))==0;
}
inline bool ovLL(L a, L b){
	return ispal(a,b) && sig(cro(a.fs-a.sc,b.fs-a.sc))==0;
}
inline bool iLL(L a, L b){		//intersect or overload
	return !ispal(a,b) || ovLL(a,b);
}
inline bool iLS(L l, L s){		//intersect(including endpoint) or overload
	return cro(l.sc-l.fs,s.fs-l.fs)*cro(l.sc-l.fs,s.sc-l.fs)<eps;
}
inline bool iLSex(L l, L s){		//intersect(excluding endpoint)
	return cro(l.sc-l.fs,s.fs-l.fs)*cro(l.sc-l.fs,s.sc-l.fs)<-eps;
}
inline bool iLP(L l, P p){		//on line
	return abs(sig(cro(l.sc-p,l.fs-p)))!=1;
}
inline bool iSS(L a, L b){		//intersect(including endpoint) or overload
	return ccw(a.fs,a.sc,b.fs)*ccw(a.fs,a.sc,b.sc)<=0 && ccw(b.fs,b.sc,a.fs)*ccw(b.fs,b.sc,a.sc)<=0;
}
inline bool iSSex(L a, L b){		//intersect(excluding endpoint)
	return ccw(a.fs,a.sc,b.fs)*ccw(a.fs,a.sc,b.sc)<0 && ccw(b.fs,b.sc,a.fs)*ccw(b.fs,b.sc,a.sc)<0;
}
inline bool iSP(L s, P p){		//intersect(including endpoint) or overload
	return ccw(s.fs,s.sc,p)==0;
}
inline D dPP(P a, P b) { return abs(a-b);}
inline D dLP(L l, P p) { return abs(perp(l,p)-p);}
inline D dLL(L a, L b) { return iLL(a,b) ? 0 : dLP(a,b.fs);}
inline D dLS(L l, L s) { return iLS(l,s) ? 0 : min(dLP(l,s.fs),dLP(l,s.sc));}
inline D dSP(L s, P p) {
	P q=perp(s,p);
	return iSP(s,q) ? abs(p-q) : min(abs(p-s.fs),abs(p-s.sc));
}
inline D dSS(L a, L b) {
	if(iSS(a,b)) return 0;
	return min(min(dSP(a,b.fs),dSP(a,b.sc)),min(dSP(b,a.fs),dSP(b,a.sc)));
}
inline P intLL(L a, L b) {	//intersection
	assert(!ispal(a,b));
	D t=cro(a.sc-a.fs,a.sc-b.fs)/cro(a.sc-a.fs,b.sc-b.fs);
	return b.fs+t*(b.sc-b.fs);
}
//
inline int iCL(C c, L l){		//num of intersection(s)
	D d=dLP(l,c.p);
	return eq(d,c.r) ? 1 : (d<c.r ? 2 : 0);
}
bool containCC(C a,C b){	//a contain b? (edge case is true)
	return abs(a.p-b.p)+b.r<a.r+eps;
}
bool containCCex(C a,C b){	//a contain b? (edge case is false)
	return abs(a.p-b.p)+b.r<a.r-eps;
}
// 交点が2個のとき、aをbが削ると思うと、削れた部分はret[0] -> res[1] (ccw) の部分
vector<P> intCC(C a,C b){
	if(abs(a.p-b.p) > a.r+b.r + eps) return {};
	if(containCCex(a,b) || containCCex(b,a)) return {};
	D d = abs(a.p-b.p);
	D tmp = (a.r*a.r+d*d-b.r*b.r)/(2.0*a.r*d);
	if(tmp < -1) tmp = -1;
	if(tmp > 1) tmp = 1;
	D theta = acos(tmp);
	P p1 = a.p+(b.p-a.p)/d*polar(a.r,-theta);
	P p2 = a.p+(b.p-a.p)/d*polar(a.r,theta);
	if(eq(p1,p2)) return {p1};
	return {p1,p2};
}
inline vector<L> tanCP(C c,P p){
	int x=large(c.r,abs(p-c.p));
	vector<L> ret;
	if(x==1) return ret;
	if(x==0){
		ret.pb(L(p,p+(c.p-p)*P(0,1)));
		return ret;
	}
	D theta=acos(c.r/abs(p-c.p));
	ret.pb(L(p,c.p+(p-c.p)/abs(p-c.p)*polar(c.r,theta)));
	ret.pb(L(p,c.p+(p-c.p)/abs(p-c.p)*polar(c.r,-theta)));
	return ret;
}
inline Pol intCL(C c,L l){
	int x=large(dLP(l,c.p),c.r);
	Pol ret;
	if(x==1) return ret;
	if(x==0){
		ret.pb(perp(l,c.p));
		return ret;
	}
	D d=dLP(l,c.p);
	if(d<eps){
		ret.pb(c.p+(l.fs-l.sc)/abs(l.fs-l.sc)*c.r);
		ret.pb(c.p-(l.fs-l.sc)/abs(l.fs-l.sc)*c.r);
		return ret;
	}
	D theta=acos(d/c.r);
	P p=perp(l,c.p);
	ret.pb(c.p+(p-c.p)/d*polar(c.r,theta));
	ret.pb(c.p+(p-c.p)/d*polar(c.r,-theta));
	return ret;
}
inline vector<L> intan(C a,C b){
	P p=(a.r*b.p+b.r*a.p)/(a.r+b.r);
	return tanCP(a,p);
}
inline vector<L> outtan(C a,C b){
	if(a.r==b.r){
		vector<L> ret;
		P p=(a.p-b.p)/abs(a.p-b.p)*polar(a.r,PI/2);
		ret.pb(L(a.p+p,b.p+p));
		ret.pb(L(a.p-p,b.p-p));
		return ret;
	}
	P p=(a.r*b.p-b.r*a.p)/(a.r-b.r);
	return tanCP(a,p);
}
D aTri(P a, P b, P c){ return cro(b-a,c-a)/2;}
D aPol(Pol p){			//点集合はCCWに与える
	int n=p.size();
	D ret=0;
	rep(i,n) ret+=cro(p[i],p[(i+1)%n])/2;
	return ret;
}
P gPol(Pol p){			//多角形内部が一様な重さを持つときの重心
	int n=p.size();
	P g;
	D s=aPol(p);
	assert(s>eps);
	rep(i,n){
		D ds=cro(p[i],p[(i+1)%n])/2;
		g+=ds/3*(p[i]+p[(i+1)%n]);
	}
	return g/s;
}
//enum ENCONT{INP=1,ONP=0,OUTP=-1};
int contain(Pol pol, P p){
	bool in=false;
	rep(i,pol.size()){
		P a=pol[i]-p,b=pol[(i+1)%pol.size()]-p;
		if(ccw(a,b,P(0,0))==0) return 0;
		if(imag(a)>imag(b)) swap(a,b);
		if(sig(imag(a))<=0 && 0<sig(imag(b)) && ccw(P(0,0),a,b)==1) in=!in;
	}
	return in ? 1 : -1;
}
L BL;
bool compBL(const P& a,const P& b){			//BL上の点をソート(BL.fs側が小さい)
	return dot(BL.sc-BL.fs,a-BL.fs)<dot(BL.sc-BL.fs,b-BL.fs);
}
bool containE(Pol pol,L l){			//polは閉集合だと思って.
	vector<P> ps;
	ps.pb(l.fs);
	ps.pb(l.sc);
	int N=pol.size();
	rep(i,N){
		L a(pol[i],pol[(i+1)%N]);
		if(ispal(a,l)) continue;
		if(!ispal(a,l)&&iSS(a,l)) ps.pb(intLL(a,l));
	}
	BL=l;
	sort(all(ps),compBL);
	int K=ps.size();
	rep(i,K-1) ps.pb((ps[i]+ps[i+1])/2.0);
	for(P p:ps) if(!contain(pol,p)) return 0;
	return 1;
}
inline D heron(D a, D b, D c){
	double s=(a+b+c)/2;
	if(s-a<eps || s-b<eps || s-c<eps) return 0;		//S=0 || 三角形できない
	return sqrt(s*(s-a)*(s-b)*(s-c));
}
inline Pol conv(Pol p){		//convex
	int n=p.size(),k=0;
	sort(all(p),compxy);
	Pol ret(2*n);
	rep(i,n){
		while(k>=2 && ccw(ret[k-2],ret[k-1],p[i])<=0) --k;
		ret[k++]=p[i];
	}
	for(int i=n-2,t=k+1;i>=0;i--){
		while(k>=t && ccw(ret[k-2],ret[k-1],p[i])<=0) --k;
		ret[k++]=p[i];
	}
	ret.resize(k-1);
	return ret;
}
inline Pol convall(Pol p){		//conv上の点全部		//点が2回以上出てくる
	int n=p.size(),k=0;
	sort(all(p),compxy);
	Pol ret(2*n);
	rep(i,n){
		while(k>=2 && ccw(ret[k-2],ret[k-1],p[i])==-1) --k;
		ret[k++]=p[i];
	}
	for(int i=n-2,t=k+1;i>=0;i--){
		while(k>=t && ccw(ret[k-2],ret[k-1],p[i])==-1) --k;
		ret[k++]=p[i];
	}
	ret.resize(k-1);
	ret.erase(unique(all(ret)),ret.end());
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N;
	D r,tm;
	V<P> p;
	{
		int x,y;
		cin >> N >> x >> y >> r >> tm;
		D theta = atan2(y,x);
		rep(i,N){
			int x,y;
			cin >> x >> y;
			p.pb(P(x,y) * polar(1.0,-theta));
		}
	}
	show(p);
	using pdd = pair<D,D>;
	V<pdd> ranges;
	rep(i,N){
		P a = p[i], b = p[(i+1)%N];
		auto inter = [&](D theta) -> bool {
			L l = {P(0,0),polar(1e5,theta)};
			if(dSP(l,a) <= r+eps || dSP(l,b) <= r+eps) return true;

			P d = (b-a)/abs(b-a) * P(0,1) * r;
			if(iSS(l, L(a+d,b+d))) return true;
			if(iSS(l, L(a-d,b-d))) return true;
			return false;
		};
		D mtheta = arg((a+b)/2.0);
		assert(inter(mtheta));
		D l,r;
		{
			D lb = mtheta - PI, ub = mtheta;
			assert(!inter(lb));
			rep(_,60){
				D mid = (lb+ub)/2;
				if(inter(mid)) ub = mid;
				else lb = mid;
			}
			l = ub;
		}
		{
			D lb = mtheta, ub = mtheta + PI;
			assert(!inter(ub));
			rep(_,60){
				D mid = (lb+ub)/2;
				if(inter(mid)) lb = mid;
				else ub = mid;
			}
			r = lb;
		}
		ranges.pb({l,r});
		shows(l,r);
	}
	{
		V<pdd> ranges2;
		rep(i,N){
			D l = ranges[i].fs, r = ranges[i].sc;
			while(l < 0) l += PI*2;
			while(r < 0) r += PI*2;
			while(l >= PI*2) l -= PI*2;
			while(r >= PI*2) r -= PI*2;
			if(l <= r) ranges2.pb({l,r});
			else{
				ranges2.pb({0,r});
				ranges2.pb({l,PI*2});
			}
		}
		ranges = ranges2;
	}
	V<D> cands;
	cands.pb(0); cands.pb(PI*2);
	for(auto r : ranges){
		cands.pb(r.fs);
		cands.pb(r.sc);
	}
	ll q = floor(tm / (PI*2));
	tm -= q * PI*2;
	cands.pb(tm);
	mkuni(cands);

	int K = cands.size()-1;
	V<bool> is(K);
	for(auto [l,r] : ranges){
		int li = lwb(cands,l), ri = lwb(cands,r);
		for(int i=li;i<ri;i++) is[i] = true;
	}
	int tmi = lwb(cands,tm);

	D ans = 0;
	rep(i,K) if(is[i]){
		D d = cands[i+1] - cands[i];
		if(i < tmi) ans += d * (q+1);
		else ans += d * q;
	}
	cout << ans << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4308kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.00000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.57079632684489656214

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4348kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.70775241662522603292

result:

ok found '2500.7077524', expected '2500.7077523', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4376kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.38424130031229475346

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 4280kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.17285976635594124673

result:

wrong answer 1st numbers differ - expected: '2500.2406700', found: '2500.1728598', error = '0.0000271'