ferinの競プロ帳

競プロについてのメモ

AGC021 B - Holes

問題ページ
B - Holes

考えたこと

  • Rがめっちゃでかいのは別に気にしなくてよさそう
  • 穴pに落ちる範囲の面積を求めて面積比を確率として求めるみたいなのを考える
  • 穴pと他の穴qの垂直二等分線を引き、穴pが属する領域の凸多角形を求めるみたいなのをやりたくなる
  • 穴pが属するのがどの領域なのかわからん
  • 垂直二等分線の交点群の凸包を取ればいいのではみたいな気持ちになるけど自明にだめ
    -----解説を見た-----
  • 穴pに落ちる範囲を角度で求める
  • 凸包を求めてその両端の穴との角度の関係を求める

幾何ができない現役ICPCerなのでつらい

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const double EPS = 1e-8;
const double INF = 1e12;
const double PI = atan(1)*4;

//point
typedef complex<double> P;
namespace std {
    bool operator < (const P& a, const P& b) {
        return real(a) != real(b) ? real(a)<real(b) : imag(a)<imag(b);
    }
    bool cmp_y(const P &a, const P &b){
        return imag(a) != imag(b) ? imag(a)<imag(b) : real(a)<real(b);
    }
}
double cross(const P& a, const P& b) {
    return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
    return real(conj(a)*b);
}
// line
struct L : public vector<P> {
    L(const P& a, const P& b) {
        push_back(a); push_back(b);
    }
};
// polygon
typedef vector<P> G;

G convex_hull(G ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end(), cmp_y);
  G r(2*n);
  for(int i = 0; i < n; i++){
    while(k>1 && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  for(int i = n-2, t = k; i >= 0; i--){
    while(k>t && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  r.resize(k-1);
  return r;
}

int x[105], y[105];
map<PII, int> mp;
double ans[105];
signed main(void)
{
  int n;
  cin >> n;
  G ps;
  REP(i, n) {
    cin >> x[i] >> y[i];
    ps.PB(P(x[i], y[i]));
    mp[{x[i], y[i]}] = i;
  }

  G poly = convex_hull(ps);
  REP(i, poly.size()) {
    P p = poly[(i==0?poly.size()-1:i-1)] - poly[i];
    P q = poly[(i==poly.size()-1?0:i+1)] - poly[i];
    double theta = PI - acos(dot(p, q)/abs(p)/abs(q));
    ans[mp[{poly[i].real(), poly[i].imag()}]] = theta/2/PI;
  }

  REP(i, n) cout << fixed << setprecision(9) << ans[i] << endl;

  return 0;
}