解いた問題のソースコードと解説など。


SRM 326 Div1 Medium InscribedTriangles

問題

半径5の円に内接する三角形の面積の最大値を求めよ。ただし、頂点は角度angleFrom[i]からangleTo[i]の間になければならない。角度は1000分の1度で与えられる。

やりかた

頂点の位置に関して4つのケースが有る。

  1. すべての頂点が、角度範囲の境界にあるとき
  2. 2つの頂点が角度範囲の境界にあるとき
  3. 1つの頂点が角度範囲の境界にあるとき
  4. どの頂点も角度範囲の境界にないとき

1.については総当りで計算

2.については残りの1つの頂点が境界ではない部分にあるということになる。その頂点が属している角度範囲の中でその頂点を動かすと当然ながら面積が変動する。その際に最も三角形の面積が大きくなりうるのは、その頂点が(どちらかの)境界まで動いた時であるため、結局のところは全部の点が境界にあることになり1.のケースに吸収されることになる。ただし、境界にある2つの頂点が結ぶ弧の、ちょうど中点に残りの頂点が置ける場合はそこで面積最大となるため、この限りではなくなる。2.ではこのケースについての面積を調べれば良い。

3. 2つの頂点が境界にないとき、この時面積が最大となるのは境界上にある点を頂点とする二等辺三角形の時である。二等辺三角形を保ちつつ2つの頂点を動かすと、最も三角形の面積が大きくなりうるのはどちらかの頂点が境界まで動いた時であるため、結局の話これは2.のケースに吸収されることになる。ただしその二等辺三角形が正三角形の形を取りうる場合にはその限りではない。ここではそのケースのみ調べればいい。

4.これは三角形の形を保ちつつ、回転させることでどれかしらの頂点を境界上に持ってくることができるので無視して良い。


注意点として、角度は0~360000の数値で与えられるので、調べる頂点の角度がそれ以上の数値なら360000引いて、一周戻してやる必要がある。

以下ソース。

#define PI acos(-1)
#define RAD(x) (x) * PI / 180000.0


class InscribedTriangles {
public:
  int N;
  vector<int> af, at;
  bool in(double x){
    for(int i = 0; i < N; i++) if(af[i] - EPS <= x && x <= at[i] + EPS) return true;
    return false;
  }

  double area(double a, double b, double c){
    if(!in(a) || !in(b) || !in(c)) return 0.0;
    double x1 = 5.0 * cos(RAD(a)), y1 = 5.0 * sin(RAD(a));
    double x2 = 5.0 * cos(RAD(b)), y2 = 5.0 * sin(RAD(b));
    double x3 = 5.0 * cos(RAD(c)), y3 = 5.0 * sin(RAD(c));
    return 0.5 * fabs(x1 * y2 - x2 * y1 + x2 * y3 - x3 * y2 + x3 * y1 - x1 * y3);
  }
  double sub(double x){
    return x > 360000 ? x - 360000 : x;
  }
  double findLargest(vector <int> angleFrom, vector <int> angleTo){
    N = angleFrom.size();
    af = angleFrom; at = angleTo;
    double ans = 0.0;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	for(int k = 0; k < N; k++){
	  ans = max(ans, area(angleFrom[i], angleFrom[j], angleFrom[k]));
	  ans = max(ans, area(angleFrom[i], angleFrom[j], angleTo[k]));
	  ans = max(ans, area(angleFrom[i], angleTo[j], angleFrom[k]));
	  ans = max(ans, area(angleFrom[i], angleTo[j], angleTo[k]));
	  ans = max(ans, area(angleTo[i], angleFrom[j], angleFrom[k]));
	  ans = max(ans, area(angleTo[i], angleFrom[j], angleTo[k]));
	  ans = max(ans, area(angleTo[i], angleTo[j], angleFrom[k]));
	  ans = max(ans, area(angleTo[i], angleTo[j], angleTo[k]));
	}

    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++){
    	ans = max(ans, area(angleFrom[i], angleFrom[j], 0.5 * (angleFrom[i] +  angleFrom[j])));
    	ans = max(ans, area(angleFrom[i], angleTo[j], 0.5 * (angleFrom[i] +  angleTo[j])));
    	ans = max(ans, area(angleTo[i], angleFrom[j], 0.5 * (angleTo[i] +  angleFrom[j])));
    	ans = max(ans, area(angleTo[i], angleTo[j], 0.5 * (angleTo[i] +  angleTo[j])));	
    	ans = max(ans, area(angleFrom[i], angleFrom[j], 
			    sub(0.5 * (angleFrom[i] +  angleFrom[j] + 360000))));
    	ans = max(ans, area(angleFrom[i], angleTo[j], sub(0.5 * (angleFrom[i] +  angleTo[j] + 360000))));
    	ans = max(ans, area(angleTo[i], angleFrom[j], sub(0.5 * (angleTo[i] +  angleFrom[j] + 360000))));
    	ans = max(ans, area(angleTo[i], angleTo[j], sub(0.5 * (angleTo[i] +  angleTo[j] + 360000))));	
      }

    for(int i = 0; i < N; i++){
      ans = max(ans, area(angleFrom[i], sub(angleFrom[i] + 120000), sub(angleFrom[i] + 240000)));
      ans = max(ans, area(angleTo[i], sub(angleTo[i] + 120000), sub(angleTo[i] + 240000)));
    }

    return ans;
  }
Get up! 明日のSUPER ST@R!