Submission #2134063

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

const double PI = acos(-1.0);

#define EPS 1.0e-8
#define INF 1.0e12
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);
}}
double inP(const P& p, const P& q){ return real(conj(p)*q); } //dot
double outP(const P& p, const P& q){ return imag(conj(p)*q); } //cross
struct L : public vector<P> {
  L(const P& a, const P& b){ push_back(a); push_back(b); }
};
typedef vector<P> G;
int ccw(P a, P b, P c){
  b-=a; c-=a;
  if(outP(b,c)>0) return +1; //counter clockwise
  if(outP(b,c)<0) return -1; //clockwise
  if(inP(b,c)<0) return +2; //c-a-b on line
  if(norm(b)<norm(c)) return -2; //a-b-c on line
  return 0;
}

G convex_hull(vector<P> &ps){
  int n=ps.size(),k=0;
  sort(ps.begin(),ps.end());
  vector<P> ch(2*n);
  for(int i=0;i<n;ch[k++]=ps[i++])
    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--])
    while(k>=t&&ccw(ch[k-2],ch[k-1],ps[i])<= 0)--k;
  ch.resize(k-1);
  return ch;
}

int main(){
  int N;
  cin >> N;

  map<vector<int>, int> memo;
  vector<P> ps;
  rep(i,N){
    int x, y;
    cin >> x >> y;
    ps.push_back(P(x,y));
    memo[{x,y}] = i;
  }
  
  G ch = convex_hull(ps);
  vector<double> ret(N,0);
  int M = ch.size();
  rep(i,M){
    int x = (int)(real(ch[i])), y = (int)(imag(ch[i]));
    int id = memo[{x,y}];

    double x_prev = real(ch[(i-1+M)%M]), y_prev = imag(ch[(i-1+M)%M]);
    double x_next = real(ch[(i+1)%M]), y_next = imag(ch[(i+1)%M]);
    
    double r1 = atan2((double)(y-y_prev), (double)(x-x_prev)) - PI/2.0;
    while(r1<-PI) r1 += 2*PI;
    while(PI<r1) r1 -= 2*PI;
    double r2 = atan2((double)(y_next-y), (double)(x_next-x)) - 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;
    
    ret[id] = range/(2*PI);
  }
  rep(i,N){
    printf("%.20lf\n", ret[i]);
  }

  return 0;
}

Submission Info

Judge Result