QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755533#9548. The Foolucup-team5008#WA 0ms3780kbC++236.0kb2024-11-16 17:35:482024-11-16 17:35:49

Judging History

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

  • [2024-11-16 17:35:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-11-16 17:35:48]
  • 提交

answer

#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define SZ(a) ll(a.size())
#define eb emplace_back
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;

bool chmax(auto& a, auto b) {return a < b ? a = b, 1 : 0; }
bool chmin(auto& a, auto b) {return a > b ? a = b, 1 : 0; }

using ld = long double;
using Point = complex<ld>;

const ld EPS = 1e-6;

constexpr Point ORIGIN(0,0);

bool equal(ld a, ld b){
	return fabsl(a-b) <= EPS;
}

bool equal(Point a, Point b){
	return equal(a.real(), b.real()) && equal(a.imag(), b.imag());
}

ld dot(Point a, Point b){
	return a.real() * b.real() + a.imag() * b.imag();
}

ld cross(Point a, Point b){
	return a.real() * b.imag() - a.imag() * b.real();
}

ld getArea(vector<Point> v){
	ld res = 0;
	int n = v.size();
	if(n == 0) return res;
	rep(i,n) res += cross(v[i], v[(i+1)%n]);
	return res * ld(0.5);
}

int contain(vector<Point> v, Point p){
	bool in = false;
	int n = v.size();
	rep(i,n){
		Point a = v[i]-p, b = v[(i+1)%n]-p;
		if(imag(a) > imag(b)) swap(a,b);
		if(imag(a) <= EPS && EPS < imag(b) && cross(a,b) < -EPS) in = !in;
		if(equal(cross(a,b), 0) && dot(a,b) <= EPS) return 1;
	}
	return in ? 2 : 0;
}

Point input(){
	ld x,y; cin >> x >> y;
	return Point(x,y);
}

Point centroid(vector<Point> v){
	ll n = v.size();
	/*
	Point res = ORIGIN;
	rep(i,n){
		res += v[i];
	}
	return res / ld(n);
	*/
	Point res = ORIGIN;
	rep(i,n-2){
		ll l = i+1;
		ll r = i+2;
		ld area = getArea({v[l], v[r], v[0]});
		Point cent = (v[l]+v[r]+v[0])/ld(3.0);
		res += cent * area;
	}
	return res / getArea(v);
}

struct Line{
	Point a, b;
	Line() = default;
	Line(Point a, Point b) : a(a), b(b) {}
};

struct Segment : Line{
	Segment() = default;
	Segment(Point a, Point b) : Line(a,b) {}
};

bool contain(Segment s, Point p){
	return dot(s.a-p, s.b-p) <= EPS;
}

vector<Point> crossPoint(Segment s, Segment t){
	ld d1 = cross(s.b-s.a, t.b-t.a);
	ld d2 = cross(s.b-s.a, s.b-t.a);
	vector<Point> res;
	if(equal(d1, 0)){
		if(equal(d2,0)){
			if(contain(s, t.a)) res.eb(t.a);
			if(contain(s,t.b)) res.eb(t.b);
			if(contain(t, s.a)) res.eb(s.a);
			if(contain(t, s.b)) res.eb(s.b);
			vector<Point> res2;
			for(auto el: res){
				bool flag = true;
				for(auto el2: res2){
					if(equal(el, el2)) flag = false;
				}
				if(flag) res2.eb(el);
			}
			res = res2;
		}
	}
	else{
		Point cand = t.a + (t.b-t.a) * d2 / d1;
		if(contain(s, cand) && contain(t,cand)) res.eb(cand);
	}
	return res;
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	cout << fixed << setprecision(15);
	ll n; cin >> n;
	ld W; cin >> W;
	vector<Point> v(n);
	rep(i,n) v[i] = input();
	Point begin = input();	
	Point cent = centroid(v);
	ld S = getArea(v);
	//cout << S << endl;
	auto move = [&](Point p){
		return (p-cent) * (W+S) / W + cent;
	};
	Point end = move(begin);
	vector<Point> f(n);
	rep(i,n) f[i] = move(v[i]);
	ll start = -1;
	rep(i,n){
		vector<Point> u = {v[i], v[(i+1)%n], begin};
		if(contain(u, cent)) start = i;
	}

	{	
		vector<Point> u = {v[(start+1)%n], v[(start+2)%n], begin};
		if(contain(u, cent)){
			start = (start+1)%n;
		}
	}

	//cout << begin << endl;
	//rep(i,n) cout << v[i] << " ";
	//cout << endl;
	//cout << end << endl;
	//rep(i,n) cout << f[i] << " ";
	//cout << endl;

	vector<ld> ans(n);
	if(contain(v, end) == 2) {
		vector<Point> cP(n);
		vl par(n);
		ll next = start;
		rep(i,n){
			ll now = (i+start)%n;
			while(true){
				Segment s(v[next], v[(next+1)%n]);
				Segment t(f[now], end);
				auto cand = crossPoint(s, t);
				if(!cand.empty()){
					assert(cand.size() == 1);
					par[now] = next;
					cP[now] = cand[0];
					break;
				}
				next = (next+1)%n;
			}
		}
		//rep(i,n) cout << par[i] << " ";
		//cout << endl;
		rep(i,n){
			vector<Point> pol;
			pol.eb(end);
			pol.eb(cP[i]);
			ll j = par[i];
			while(par[i] != par[(i+1)%n]){
				if(j == par[(i+1)%n]) break;
				j = (j+1)%n;
				pol.eb(v[j]);
			}
			pol.eb(cP[(i+1)%n]);
			ans[i] = getArea(pol) / S;
		}
	}
	else{
		vector<vector<Point>> cP(n);
		vvl par(n);
		{
			ll next = (start+2)%n;
			rep(i,n){
				ll now = (i+start)%n;
				ll cnt = 0;
				while(cross(v[next]-end, f[now]-end) >= -EPS){
					next = (next+1)%n;
					cnt++;
					if(cnt >= 2 * n) goto XYZ;
				}
				Segment s(v[next], v[(next+n-1)%n]);
				Segment t(f[now], end);
				auto cand = crossPoint(s, t);
				if(!cand.empty()){
					assert(SZ(cand) == 1);
					cP[now].eb(cand[0]);
					par[now].eb(next);
				}
			}
			XYZ:;
		}
		{
			ll next = start;
			rep(i,n){
				ll now = (i+start)%n;
				ll cnt = 0;
				while(cross(v[next]-end, f[now]-end) >= -EPS){
					next = (next+n-1)%n;
					cnt++;
					if(cnt >= 2 * n) goto XYZ2;
				}
				Segment s(v[next], v[(next+1)%n]);
				Segment t(f[now], end);
				auto cand = crossPoint(s, t);
				if(!cand.empty()){
					assert(SZ(cand) == 1);
					cP[now].eb(cand[0]);
					par[now].eb(next);
				}
			}
			XYZ2:;
		}
		rep(i,n){
			ll l = i, r = (i+1)%n;
			vector<Point> pol;
			if(SZ(cP[l]) < 2){
				if(SZ(cP[r]) < 2) continue;
				pol.eb(cP[r][1]);
				ll j = par[r][1];
				par[r][0] = (par[r][0]+n-1)%n;
				while(true){
					if(j == par[r][0]) break;
					j = (j+1)%n;
					pol.eb(v[j]);
				}
				pol.eb(cP[r][0]);
			}
			else if(SZ(cP[r]) < 2){
				pol.eb(cP[l][0]);
				ll j = par[l][0];
				j = (j+n-1)%n;
				while(true){
					if(j == par[l][1]) break;
					j = (j+1)%n;
					pol.eb(v[j]);
				}
				pol.eb(cP[l][1]);
			}
			else{
				pol.eb(cP[l][1]);
				pol.eb(cP[l][0]);
				ll j = par[l][0];
				j = (j+n-1)%n;
				par[r][0] = (par[r][0]+n-1)%n;
				while(true){
					if(j == par[r][0]) break;
					j = (j+1)%n;
					pol.eb(v[j]);
				}
				pol.eb(cP[r][0]);
				pol.eb(cP[r][1]);
				j = par[r][1];
				while(true){
					if(j == par[l][1]) break;
					j = (j+1)%n;
					pol.eb(v[j]);
				}
			}
			cout << i << endl;
			for(auto el: pol) cout << el << " ";
			cout << endl;
			ans[i] = getArea(pol) / S;
		}

	}
	rep(i,n) cout << ans[i] << "\n";
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3780kb

input:

3 5 3
QWQQWQQWQQWQQWQ
QWQQWQQWQQWQQWQ
QWQQWQQWQQWQQwQ

output:

0.000000000000000
0.000000000000000
0.000000000000000

result:

wrong answer 1st lines differ - expected: '3 5', found: '0.000000000000000'