1089-Strawberry Cake

問題概要

日本語なので略

解法

適当に区間を決めて二分探索する．

実装(C++)

int n;
Polygon P;
double S;

bool input(){
  cin>>n;
  if(n==0)return false;
  P=Polygon(n);
  for(int i=0;i<n;i++)cin>>P[i];
  S=area(P);
  return true;
}

double calc_area(double phi){
  Line t(0,0,cos(phi),sin(phi));
  Polygon p=convex_cut_left(P,t);
  return area(p)/S;
}

void output(double phi){
  cout<<setprecision(15)<<setiosflags(ios::fixed);
  cout<<cos(phi)*100<<" "<<sin(phi)*100<<endl;
}
double D=0.01;
int main(){
  while(input()){
    double low,high,mid;
    double now=0;
    REP(i,1000){
      if(calc_area(now)<=0.5&&calc_area(now+D)>=0.5){
        low=now,high=now+D;
        REP(j,5000){
          mid=(low+high)/2;
          if(calc_area(mid)<=0.5){
            low=mid;
          }else{
            high=mid;
          }
        }
        break;
      }
      now+=D;
    }
    output(mid);
  }
}