QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729799 | #9576. Ordainer of Inexorable Judgment | ucup-team159# | WA | 1ms | 4468kb | C++23 | 10.2kb | 2024-11-09 17:51:02 | 2024-11-09 17:52:07 |
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:51:02]
- 提交
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 = long 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-11,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+D(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;
}
void solve(){
int N;
D r,tm;
V<P> p;
{
int x,y;
if(cin >> N >> x >> y >> r >> tm){
}else{
exit(0);
}
D theta = atan2(y,x);
rep(i,N){
int x,y;
cin >> x >> y;
p.pb(P(x,y) * polar<D>(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<D>(5e4,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)/D(2.0));
assert(inter(mtheta));
D l,r;
{
D lb = mtheta - PI, ub = mtheta;
assert(!inter(lb));
rep(_,40){
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(_,40){
D mid = (lb+ub)/2;
if(inter(mid)) lb = mid;
else ub = mid;
}
r = lb;
}
ranges.pb({l,r});
assert(r-l < PI*2);
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;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !!
cout << fixed << setprecision(20);
while(true) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4264kb
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: 4276kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.57079632679775385042
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.70775226656998491137
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4468kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.38424129419934483420
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 4384kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
2500.23305548731231207071
result:
wrong answer 1st numbers differ - expected: '2500.2406700', found: '2500.2330555', error = '0.0000030'