QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379882#7778. Turning Permutationucup-team2230#WA 0ms3844kbC++235.8kb2024-04-06 19:41:032024-04-06 19:41:04

Judging History

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

  • [2024-04-06 19:41:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-04-06 19:41:03]
  • 提交

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