naoya_t@topcoder

GCJ 2010 Round 2 : D. Grazing Google Goats

12:32 |

長らくハマってしまい敗退の原因となった問題D。

比較的容易と思って飛びついたD-smallでしたが、結果が合わないのは精度の問題でした。long doubleで解決するような話。

教訓

浮動小数点数の精度とかたまには考えたほうがいいよ。long doubleかわいいよlong double

• 1位のbmerryのコード(AC)をダウンロードしてsmallのデータを食わせてみたら自分のと随分違う値が出てる
• あー。これってもしかしてdoubleの計算誤差かー！！！
• double変数をlong doubleに置き換える。
  • sin→sinl,cos→cosl,hypot→hypotlなど
• で、とりあえずsmallはAC

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

typedef long double ldouble;
typedef pair<ldouble,ldouble> dd;

int N,M;
vector<dd> p,q;

ldouble hypot(dd x1, dd x2){
  return hypotl(x1.first-x2.first, x1.second-x2.second);
}
ldouble yogen(ldouble a,ldouble b,ldouble c){
  return acosl((a*a+b*b-c*c)/(a*b*2));
}
ldouble ougi(ldouble r,ldouble th=M_PI*2){
  return th*r*r/2;
}
ldouble deg(ldouble rad){
  return 180.0*rad/M_PI;
}
ldouble area2(int m){
  dd qm = q[m];
  dd p0=p[0], p1=p[1];
  ldouble r0=hypot(p0,qm), r1=hypot(p1,qm), d=hypot(p0,p1);
  if(r0<r1) { swap(r0,r1); swap(p0,p1); } // r0 > r1に揃える
  ldouble theta=yogen(r0,r1,d);
  ldouble th0=yogen(r0,d,r1), th1=yogen(r1,d,r0);
  ldouble h=r0*sinl(th0);

  if (r0+r1==d) {
    return 0; // midpoint
//} else if (th1 <= M_PI/4) {
//  return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
  } else if (r0<r1+d) {
    return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
  } else {
    return ougi(r1);
  }
  
  return m;
}

int main(){
  int T;cin>>T; // S:1-100  L:1-10
  rep(t,T){
    p.clear(); q.clear();
    cin>>N>>M;
    rep(n,N){ double x,y; cin>>x>>y; p.pb( dd(x,y) ); } // S:2    L:2-5000
    rep(m,M){ double x,y; cin>>x>>y; q.pb( dd(x,y) ); } // S:1-10 L:1-1000

    printf("Case #%d:", 1+t);
    rep(m,M) printf(" %.9Lf", area2(m));
    printf("¥n");
  }
  return 0;
}