QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379882 | #7778. Turning Permutation | ucup-team2230# | WA | 0ms | 3844kb | C++23 | 5.8kb | 2024-04-06 19:41:03 | 2024-04-06 19:41:04 |
Judging History
answer
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using uint=unsigned;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define si(x) int(x.size())
#define a first
#define b second
template<class t>using vc=vector<t>;
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;}else return false;}
template<class t,class u>
ostream& operator<<(ostream&os,const pair<t,u>&p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t>ostream& operator<<(ostream&os,const vector<t>&v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
using P=pair<int,int>;
using vi=vc<int>;
const uint mod = 1000000007;
struct mint{
uint v;
mint(ll vv=0){s(vv%mod+mod);}
mint& s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
mint operator-()const{return mint()-*this;}
mint&operator+=(mint r){return s(v+r.v);}
mint&operator-=(mint r){return s(v+mod-r.v);}
mint&operator*=(mint r){v=(unsigned long long)v*r.v%mod;return *this;}
mint&operator/=(mint r){return *this*=r.inv(); }
mint operator+(mint r)const{return mint(*this)+=r;}
mint operator-(mint r)const{return mint(*this)-=r;}
mint operator*(mint r)const{return mint(*this)*=r;}
mint operator/(mint r)const{return mint(*this)/=r;}
mint pow(ll n)const{
if(n<0)return inv().pow(-n);
mint res(1),x(*this);
while(n){
if(n&1) res*=x;
x*=x;
n>>=1;
}
return res;
}
mint inv()const{return pow(mod-2);}
};
#define mp make_pair
using ld=long double;
const ld eps = 1e-9;
int sgn(ld a){ return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
using pt=complex<ld>;
#define x real()
#define y imag()
ld dot(const pt&a,const pt&b){return a.x*b.x+a.y*b.y;}
ld crs(const pt&a,const pt&b){return a.x*b.y-a.y*b.x;}
ld crs(const pt&a,const pt&b,const pt&c){return crs(b-a,c-a);}
int ccw(const pt&a,const pt&b){return sgn(crs(a,b));}
int ccw(const pt&a,const pt&b,const pt&c){return ccw(b-a,c-a);}
int argtype(const pt&a){
if(sgn(a.y)==0)return a.x<0?1:0;
return a.y<0?0:1;
}
int argcmp(const pt&a,const pt&b){
int at=argtype(a),bt=argtype(b);
if(at!=bt) return at<bt?-1:1;
return -ccw(a,b);
}
using ln=pair<pt,pt>;
pt dir(ln a){return a.b-a.a;}
pt eval(ln a,ld b){return a.a+dir(a)*b;}
ld crs(ln a,pt b){return crs(a.a,a.b,b);}
int ccw(ln a,pt b){return ccw(a.a,a.b,b);}
pt cll(ln a, ln b){
return eval(a,crs(b.a,b.b,a.a)/crs(dir(a),dir(b)));
}
vc<pt>halfpint(vc<ln>s){
sort(all(s),[&](ln a,ln b){
int c = argcmp(dir(a),dir(b));
if(c) return c<0;
return ccw(b,a.a)>0;
});
s.erase(unique(all(s),[&](ln a,ln b){
return argcmp(dir(a),dir(b)) == 0;
}), s.end());
int n = si(s);
vi cur;
rep(ii,n*2){
int i=ii%n,m;
while((m=si(cur))>=2){
if(ccw(s[i],cll(s[cur[m-2]],s[cur[m-1]]))>0) break;
cur.pop_back();
}
cur.pb(i);
}
vi cnt(n);
for(auto i:cur) cnt[i]++;
vc<ln>t;
rep(i,n) if(cnt[i]==2) t.pb(s[i]);
int m = si(t);
vc<pt>res(m);
rep(i,m) res[i]=cll(t[i],t[(i+1)%m]);
return res;
}
void solve(){
ld xl,yl,xr,yr;
cin>>xl>>yl>>xr>>yr;
int n;cin>>n;
vc<pt>vec(n);
rep(i,n){
ld p,q;cin>>p>>q;
vec[i] = pt(p,q);
}
vc<ln>V;
V.eb(pt(xl,yl), pt(xr,yl));
V.eb(pt(xr,yl), pt(xr,yr));
V.eb(pt(xr,yr), pt(xl,yr));
V.eb(pt(xl,yr), pt(xl,yl));
ld area[2] = {}, ans = 0;
rep(i,n){
auto c=[&](vc<pt>ci, int id){
if(si(ci) >= 3){
ld A = 0;
rng(ii,1,si(ci)-1) A += crs(ci[0],ci[ii],ci[ii+1]);
area[id] += A;
if(id == 0) ans -= A * (vec[i].x * vec[i].x + vec[i].y * vec[i].y);
else ans += A * (vec[i].x * vec[i].x + vec[i].y * vec[i].y);
//cout << ans << " " << area[id] << endl;
rep(_,2){
int ymx,ymn; pair<ld,ld>curmx=mp(-1e9,-1e9), curmn=mp(1e9,1e9);
rep(j,si(ci)){
ld pp = ci[j].x, qq = ci[j].y;
if(curmx < mp(pp,qq)){
curmx = mp(pp,qq); ymx = j;
}
if(curmn > mp(pp,qq)){
curmn = mp(pp,qq); ymn = j;
}
}
//cout << curmx << " " << curmn << " " << ymx << " "<< ymn << endl;
//bool up = 1;
int nn = si(ci);
ld uv;
if(_ == 0) uv = vec[i].x;
else uv = vec[i].y;
rep(ii,nn){
int now = (ymx+ii)%nn;
//if(now == ymn) up = 0;
int nxt = (now+1)%nn;
ld ri = ci[now].y, le = ci[nxt].y;
ld xxr = ci[now].x, xxl = ci[nxt].x;
if(sgn(xxr,xxl) == 0) continue;
ld a = (le-ri) / (xxl-xxr);
//cout << le << ' ' << ri << ' ' << xxl << ' ' << xxr << ' ' << a << endl;
if(sgn(a) == 0){
if(id == 0) ans += 2.0L*uv*(le*le/2.0L*(xxr-xxl));
else ans -= 2.0L*uv*(le*le/2.0L*(xxr-xxl));
}
else{
if(id == 0) ans += 2.0L*uv*(ri*ri*ri-le*le*le)/6.0L/a;
else ans -= 2.0L*uv*(ri*ri*ri-le*le*le)/6.0L/a;
}
}
for(auto &e:ci){
ld xx = e.x, yy = e.y;
e = pt(yy, xx);
}
}
}
};
//close
vc<ln>cur = V;
rep(j,n){
if(i == j) continue;
pt md = (vec[i]+vec[j])/2.0L;
auto nxny = vec[i]-vec[j];
pt dr = pt(nxny.y,-nxny.x);
cur.eb(md, md+dr);
}
vc<pt>ci = halfpint(cur);
c(ci, 0);
//far
cur = V;
rep(j,n){
if(i == j) continue;
pt md = (vec[i]+vec[j])/2.0L;
auto nxny = vec[j]-vec[i];
pt dr = pt(nxny.y,-nxny.x);
cur.eb(md, md+dr);
}
ci = halfpint(cur);
c(ci, 1);
}
ans /= area[0]/2.0L;
ans *= acos(-1.0L);
cout << ans << endl;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
int t;t=1;//cin>>t; t=1;//
while(t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3844kb
input:
3 2
output:
nan
result:
wrong output format Expected integer, but "nan" found