QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755533 | #9548. The Fool | ucup-team5008# | WA | 0ms | 3780kb | C++23 | 6.0kb | 2024-11-16 17:35:48 | 2024-11-16 17:35:49 |
Judging History
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'