SRM 225 DIV1 Hard Triangulation
問題
(凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。
引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない
解答
まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順greedyでおｋ。
あとは適当に「既に引いた対角線と交差せず」「多角形自身と交差せず」「多角形の内側にある」かどうかを判定したい。
これは整数幾何でがんばる
コメント
コードのコメントのとおり、「多角形の内側にある」判定で適当なことをしているが、Practice Roomのrng_58さんの解答では面積に着目しているようだ。
コード
#include <string> #include <vector> #include <algorithm> #include <sstream> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) using namespace std; typedef vector<pair<int,int> > vpii; typedef long long ll; typedef vector<string> vs; struct P { typedef int T; typedef ll T2; //T2は{a*b | a:T, b:T}を含むタイプ T x, y; P(T x_, T y_): x(x_), y(y_) {} P(): x(0), y(0) {} }; inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; } inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); } inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); } inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; } inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; } struct L { P a, b; L(const P &a_, const P &b_): a(a_), b(b_) {} const P& operator[](size_t i) const { return i ? b : a; } }; inline int ccw(const P& a, const P& b, const P& c) { int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y; P::T2 t = (P::T2)ax*by - (P::T2)ay*bx; if (t > 0) return 1; if (t < 0) return -1; if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2; if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2; return 0; } int intersectSS(const L &s, const L &t) { int a = ccw(s.a,s.b,t.a), b = ccw(s.a,s.b,t.b), c = ccw(t.a,t.b,s.a), d = ccw(t.a,t.b,s.b); int x = a * b, y = c * d; if(x == -1 && y == -1) return 0; // cross else if( ((abs(b) == 1 || b == -2) && s.b == t.a) || ((abs(b) == 1 || b == 2) && s.a == t.a) || ((abs(a) == 1 || a == -2) && s.b == t.b) || ((abs(a) == 1 || a == 2) && s.a == t.b) ) return 2; // point overlap else if( (x == 0 && (abs(a) + abs(b) == 1)) || (y == 0 && (abs(c) + abs(d) == 1)) ) return 2; // point overlap else if(x <= 0 && y <= 0) return 0; //line overlap else return 1; } bool contains(const vector<P>& o, const P& p) { bool in = false; for (int i = 0; i < o.size(); ++i) { P a = o[i] - p, b = o[(i+1)%o.size()] - p; if (a.y > b.y) swap(a, b); if (a.y <= 0 && 0 < b.y) if (cross(a, b) < 0) in = !in; if (cross(a, b) == 0 && dot(a, b) <= 0) return true; //point on edge } return in; } struct Triangulation { vector <string> triangulate(vector <int> x, vector <int> y) { int n = x.size(); vector<P> p, p2; rep(i, n) p.pb(P(x[i], y[i])), p2.pb(p[i] + p[i]); vector<L> lines, pl; rep(i, n) pl.pb(L(p[i], p[(i+1)%n])); vpii v; //greedyにやる rep(ii, n-3) { rep(j, n) reu(k, j+1, n) { L s = L(p[j], p[k]); bool b = true; int pcount = 0; rep(l, n) { int c = intersectSS(pl[l], s); b &= c != 0; if(c == 2) pcount ++; } each(l, lines) b &= intersectSS(*l, s) != 0; //多角形の内側に線分があるかどうか。 //多角形と交差していないなら、線分の適当な場所の点が多角形の内側にあるか見ればいい。 //ここではちょうど半分の点でやっている。整数でやるために多角形も2倍 b &= contains(p2, s[0] + s[1]); //始点と終点の周囲以外で触れてたら駄目 b &= pcount == 4; if(b) { lines.pb(s); v.pb(mp(j, k)); goto next; } } next:; } vs r; each(i, v) { stringstream ss; ss << i->first << " " << i->second; r.pb(ss.str()); } return r; } };
SRM 226 DIV1 Hard TestScores
問題
いくつかの質問の回答率が与えられる。
このテストの平均点と標準偏差を求めて、回答数から"standardized score"を求めよ
"standardized score" = 1000 + 300 * (回答数 - 平均) / 標準偏差
解答
あまりよくわかってない。
自分は標準偏差を、なんとなくDPをやって求めたらできた。
しかし簡単に(sqrt$ sum [ q * (1-q) | q <- questions])と求められるらしい
コメント
わかってなくてもなんとなくDPできたのはいいと思う。
でも標準偏差くらいの知識はあろうよ…
"standardized score"も式がわからなかったり。ふつうにぐぐったら良かったか
コード
#include <vector> #include <numeric> #include <cmath> #include <cstring> #define all(o) (o).begin(), (o).end() #define mset(m,v) memset(m,v,sizeof(m)) using namespace std; double dp[55][55]; struct TestScores { vector<double> q; int n; double m; int s; double rec(int i, int score) { if(dp[i][score] == dp[i][score]) return dp[i][score]; if(i == n) return (score - m) * (score - m); double p = q[i]; return dp[i][score] = p * rec(i+1, score+1) + (1-p) * rec(i+1, score); } double weightedScore(vector <double> questions, int testScore) { q = questions, n = q.size(), m = accumulate(all(q), 0.), s = testScore; mset(dp, -1); double dev = sqrt(rec(0, 0)); return 1000 + 300 * ((testScore - m) / dev); } };
SRM 227 DIV1 Hard QuadrilateralSearch
問題
直径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; } };
