UVa 111 : History Grading

問題リンク : History Grading

問題概要：
歴史のテストをした
n個の年代順のイベント１...nがどの順番で行われるかの答えと生徒の解答があたえられる
生徒が得たスコアを計算せよ
スコアの計算方法は以下の通り
1 2 3 4 が答えだとする
生徒が 1 3 2 4と解答したとする
この２つの解答の最長増加部分列がスコアとなる
よってこの生徒は３点を得る（1 2 4 or 1 3 4）

解法：
LCSかLISをする
だけなのだが、入力が紛らわしいので注意
入力で
3 1 2 4 9 5 10 6 8 7と与えられたとき、
これはそれがそのまま解答となるわけではない
これは、イベント１は３番目に、イベント２は１番目、イベント３は２番目。。。を言う事である
つまり、解答は
2 3 1 4 6 8 10 9 5 7 となる
これでLISまたはLCSをする

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

int n;

int LCS(vector<int> &a,vector<int> &b)
{
  int dp[a.size()+1][b.size()+1];
  rep(i,a.size()+1)rep(j,b.size()+1)dp[i][j] = 0;

  rep(i,a.size())
    {
      rep(j,b.size())
	{
	  if(a[i] == b[j])dp[i+1][j+1] = dp[i][j] + 1;
	  else dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]); 
	}
    }

  return dp[a.size()][b.size()];
}

int main()
{
  scanf("%d",&n);
  vector<int> answer(n);
  rep(i,n)scanf("%d",&answer[i]);
  vector<int> result(n);
  rep(i,n)result[answer[i]-1] = i;

  vector<int> person(n);
  while(scanf("%d",&person[0])!=EOF)
    {
      REP(i,1,n)scanf("%d",&person[i]);
      vector<int> input(n);
      rep(i,n)input[person[i]-1] = i;
      printf("%d\n",LCS(result,input));
    }

  return 0;
}||<

*1385141995*[UVa][幾何]
問題リンク：[http://uva.onlinejudge.org/external/1/109.html:title]

問題概要：
N個の王国の情報と複数のミサイルの情報が与えられる
ミサイルが着弾した王国の面積の総和を求めよ

解法：
各王国の点の情報をとった後に凸包をとる
ミサイルの入力をとりつつ、凸多角形のいずれかの内部に着弾するかどうかを判定する
（点に対する多角形の内包判定を行う）
あとは着弾した凸多角形の面積を足していき出力する

コード：
>|c|

//幾何ライブラリ

Polygon poly[MAX];

int main()
{
  int n,index=0;
  while(scanf("%d",&n), n!=-1)
    {
      rep(i,n)
	{
	  int x,y;
	  scanf("%d %d",&x,&y);
	  poly[index].push_back(Point(x,y));
	}
      poly[index] = andrewScan(poly[index]);
      index++;
    }

  bool destroy[index];
  rep(i,index)destroy[i] = false;
  Point missile;
  while(scanf("%lf %lf",&missile.x,&missile.y) != EOF)
    {
      rep(i,index)
	{
	  if(destroy[i])continue;
	  if(inPolygon(poly[i],missile))
	    {
	      destroy[i] = true;
	      break;
	    }
	}
    }

  double ans = 0;
  rep(i,index)if(destroy[i])
    {
      ans += getArea(poly[i]);
    }
  printf("%.2lf\n",ans);
  return 0;
}