Submission #2134465

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
const double EPS = 1e-8, INF = 1e12, PI = 2 * acos(0.0);
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 operator == (const P& a, const P& b) { return abs(real(a) - real(b)) < EPS && abs(imag(a) - imag(b)) < EPS; }
    P operator / (const P& a, const double& b) { return P(real(a) / b, imag(a) / b); }
    P operator * (const P& a, const double& b) { return P(real(a) * b, imag(a) * 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); }
struct L : public vector<P> { L() {} L(const P &a, const P &b) { push_back(a); push_back(b); } };
typedef vector<P> G;
struct C { P p; double r; C() {} C(const P &p, double r) : p(p), r(r) {} };
int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return 0;       // counter clockwise
	if (cross(b, c) < 0)   return 1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}
P rotate(P vec, double ang) {
    double x = real(vec), y = imag(vec);
    return P(x * cos(ang) - y * sin(ang), x * sin(ang) + y * cos(ang));
}
bool intersectLL(const L &l, const L &m) {
    return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
        abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;   // same line
}
bool intersectLS(const L &l, const L &s) {
    return cross(l[1] - l[0], s[0] - l[0])*       // s[0] is left of l
        cross(l[1] - l[0], s[1] - l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const P &p) {
    return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSS(const L &s, const L &t) {
    return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
        ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}
bool intersectSP(const L &s, const P &p) {
    return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}
bool intersectSSwithoutPoint(const L &s, const L &t) { // not verified
    return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) < 0 &&
        ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) < 0;
}
P crosspoint(const L &l, const L &m) {
    double A = cross(l[1] - l[0], m[1] - m[0]);
    double B = cross(l[1] - l[0], l[1] - m[0]);
    if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
    if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
    return m[0] + B / A * (m[1] - m[0]);
}
double argument(const P &a, const P &b) { // argument for A->B[-PI,PI]
    double ax = real(a), ay = imag(a), bx = real(b), by = imag(b);
    return atan2(by - ay, bx - ax);
}
double threePointArgument(const P &a, const P &b, const P &c) { // argument for A->B->C
    P ba = b - a;
    P cb = c - b;

    double r1 = atan2(real(ba), imag(ba)) - PI / 2.0;
    while (r1<-PI) r1 += 2 * PI;
    while (PI<r1) r1 -= 2 * PI;
    double r2 = atan2(real(cb), imag(cb)) - PI / 2.0;
    while (r2<-PI) r2 += 2 * PI;
    while (PI<r2) r2 -= 2 * PI;

    //cout << id << "\t" << r1 << "\t" << r2 << endl;

    double range = 0;
    if (r1 >= 0 && r2>0) range = r2 - r1;
    else if (r1<0 && r2 >= 0) range = -r1 + r2;
    else if (r1 >= 0 && r2<0) range = (PI - r1) + (PI + r2);
    else range = r2 - r1;

    return range;
}
G convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	G ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) // upper-hull
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N;
P po[101];
double ans[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<P> v;
    rep(i, 0, N) {
        double x, y; cin >> x >> y;
        po[i] = P(x, y);
        v.push_back(po[i]);
    }

    if (N == 2) {
        printf("0.5\n0.5\n");
        return;
    }

    auto ch = convex_hull(v);
    int n = ch.size();
    rep(i, 0, n) {
        int a = i;
        int b = (i + 1) % n;
        int c = (i + 2) % n;

        int id = -1;
        rep(j, 0, N) if (abs(po[j] - ch[b]) < EPS) id = j;
        ans[id] = threePointArgument(ch[a], ch[b], ch[c]) / (2.0 * PI);
    }

    rep(i, 0, N) printf("%.10f\n", ans[i]);
}

Submission Info

Judge Result