多角形の頂点がn個反時計回りに与えられる。 多角形の各頂点と多角形の内側の点Cを端点とする線分が 全て多角形の内側にあるような点Cが存在するような 多角形をstar shapeとする。 与えられた多角形がstar shapeであるかどうか判定する問題。 十分に大きい…

n個の黒い点とm個の白い点が与えられる。 黒い点と白い点を1本の直線でわけることが できるかどうかを判定する問題。 黒い点と白い点をそれぞれを凸包してから 2つの多角形が交差するかどうか判定した。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #incl</climits></vector></iostream></algorithm></cmath>…

蟻本を参考にした。 ビットDPで解いた。 dp[使った乗車券の集合][都市の番号]:=最小コスト #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #define INF (1<<29) using namespace std; int main(void){ int n,m,p,a,b,x,y,z,in; double dp[(1<<8)][31],graph[31][31]; </cstdio></algorithm></vector></iostream>…