SRM 227 DIV1 Hard QuadrilateralSearch

問題 Editorial

問題

直径dの円周上のcつの点を与えられる。
この点のどれか4つを選んで四角形を作るとき、面積を最大化せよ

• 1 <= d <= 1000
• 4 <= c <= 500

解答

四角形は2つの三角形に分けられる。
対角線上の頂点を2つ全探索したら、その左右で3,4つ目の点を独立に選べる。
3,4つ目の点は全探索してもいいし、凸なので二分探索してもいい

コメント

左右を独立して選べるというのは簡単なアイデアなのに思いつけなかった。
四角形が出たら三角形に分割してみよう。
あと、一回面積計算の三角関数で誤差Fail。三角関数を使う時はとりあえずlong doubleにしておこう

コード

#include <vector>
#include <algorithm>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
using namespace std;
typedef vector<int> vi; typedef long long ll; typedef long double ld;
double cross[1111][1111];
struct QuadrilateralSearch {
	vi v;
	double maxTriangle(int i, int j) {
		double r = 0;
		rer(k, i+1, j-1) r = max(r, cross[i][k] + cross[k][j] + cross[j][i]);
		return r;
	}
	double findLargest(int d, int n, int c, int g) {
		const ld pi = acos(-1.);
		rep(k, c) v.pb((ll)k * g % n);
		sort(all(v));
		rep(k, c) v.pb(v[k] + n);
		double r = 0;
		rep(i, c*2) rep(j, c*2) cross[i][j] = imag(conj(polar(ld(d/2.), v[i]*pi*2/n)) * polar(ld(d/2.), v[j]*pi*2/n));
		rep(i, c) rer(j, i+2, c+i-2) {
			r = max(r, maxTriangle(i, j) + maxTriangle(j, i + c));
		}
		return r / 2;
	}
};