会津大学オンラインジャッジ 問122

Summer of Phyonkichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

カエルのぴょんきちが夏を乗り切れるかをこたえる問題。
動的計画法で十分です。



#include<stdio.h>
#include<set>
#include<stdlib.h>

struct S{
int x,y;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return y<s.y;
}
};

void search(int x,int y){
S s1;
s1.x=x;
s1.y=y;
std::set<S> sets[2];
sets[0].insert(s1);
int n;
scanf("%d",&n);
int dx[]={ 2, 2, 2, 1, 1, 0, 0,-1,-1,-2,-2,-2};
int dy[]={ 1, 0,-1, 2,-2, 2,-2, 2,-2, 1, 0,-1};
int sx,sy,now,next;
for(int i=0;i<n;i++){
scanf("%d %d",&sx,&sy);
now =i%2;
next=(i+1)%2;
for(std::set<S>::iterator it=sets[now].begin();it!=sets[now].end();it++){
s1=(*it);
for(int j=0;j<12;j++){
s1.x+=dx[j];
s1.y+=dy[j];
if(0<=s1.x||s1.x<=9||0<=s1.y||s1.y<=9){
if(abs(sx-s1.x)<=1&&abs(sy-s1.y)<=1){
sets[next].insert(s1);
}
}
s1.x-=dx[j];
s1.y-=dy[j];
}
}
sets[now].clear();
}
printf("%s\n",sets[next].empty()==false?"OK":"NA");
}

int main(){
int x,y;
while(scanf("%d %d",&x,&y)!=EOF){
if(x==0&&y==0)break;
search(x,y);
}
}

会津大学オンラインジャッジ問121

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121

セブンパズルを題材にした問題。



平凡な問題なので平凡なコードで平凡な順位。

平凡な問題と考え
平凡なコードで理解をし
平凡なコードの手順を考え
平凡なコードを実装し
平凡なコードを提出し
平凡な結果を期待し
平凡な順位に落ち着く。
私こそミスター平凡。


完全ハッシュ関数を実装すればもう少し早くはなるとおもいます。



#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>

struct S{
int zeroP,count;
int board[8];
bool operator<(const S& s)const{
for(int i=0;i<8;i++){
if(board[i]!=s.board[i])return board[i]<s.board[i];
}
return false;
}
};

int main(){
int moves[8][3]={{0,1,4},
{0,2,5},
{1,6,3},
{2,7,3},
{0,5,4},
{1,4,6},
{2,5,7},
{3,6,7}};
S s,s2;
s.zeroP=0;
s.count=0;
for(int i=0;i<8;i++){
s.board[i]=i;
}
std::map<S,int> memo;
std::queue<S> qu;
qu.push(s);
while(qu.empty()==false){
s=qu.front();
qu.pop();
if(memo.find(s)!=memo.end())continue;
memo[s]=s.count;
s.count++;

for(int i=0;i<3;i++){
s2=s;
s2.zeroP=moves[s.zeroP][i];
if(s.zeroP==s2.zeroP)continue;
std::swap(s2.board[s.zeroP],s2.board[s2.zeroP]);
if(memo.find(s2)!=memo.end())continue;
qu.push(s2);
}
}
while(1){
if(scanf("%d",&s.board[0])==EOF)break;
for(int i=1;i<8;i++){
scanf("%d",&s.board[i]);
}
printf("%d\n",memo[s]);
}
}

プロジェクトオイラー 失敗作 問258

プロジェクトオイラー問258を解くコードを書こうとして失敗しました。


解法
数字列を2000個ごとで一行として、その行から次の行を求める漸化式を考えます。
漸化式を立てると一行先を求める漸化式の係数から2行先を求める漸化式の係数が。
2行先を求める漸化式の係数から4行先がと求まります。
以後同じ処理を繰り返すことで2倍2倍で増える先の行を求める漸化式が手に入ります。
がこれは10＾18をそのまま愚直に求めるのより単純計算200万倍速いだけで、ループ処理が入るのでさらに遅くなり、コードを実行したところ正しい答えが出るまで23時間もかかりました。
私の使ってるパソコンかＢＣＣ5.5どちらが悪いのかわかりませんがコンパイル結果のＭｏｄ演算が妙に遅いということを加味してもこれは恥ずべき結果です。




#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>


const int LIMITER=2000;
const __int64 MOD=20092010;

struct Vec{
__int64 es[LIMITER];
void add_and_mult(Vec& v,int t){
for(int i=0;i<LIMITER;i++){
es[i]=(es[i]+v.es[i]*t)%MOD;
}
}
void reset(){
memset(es,0,sizeof(es));
}
};

int main(){
std::vector<Vec> dp[2];
Vec v1,v2,v3;
__int64 row=pow(10,18);
row=row/LIMITER;
std::cout<<row<<"\n";
v1.reset();
for(int i=0;i<LIMITER;i++){
dp[1].push_back(v1);
}

for(int i=0;i+1<LIMITER;i++){
v1.reset();
v1.es[i]=v1.es[i+1]=1;
dp[0].push_back(v1);
}
v1.reset();
v1.es[0]=v1.es[1]=v1.es[LIMITER-1]=1;
dp[0].push_back(v1);

__int64 rowData[2][LIMITER];
for(int i=0;i<LIMITER;i++)rowData[0][i]=1;
__int64 add,ans=1;
int turn=0;
int point=0;
while(row>0){
std::cout<<"\n row="<<row<<" ";
if(row%2==1){
int now=point;
int next=(point+1)%2;
int now1=turn%2;
memset(rowData[next],0,sizeof(rowData[next]));
for(int i=0;i<LIMITER;i++){
for(int j=0;j<LIMITER;j++){
add=(rowData[now][j]*dp[now1][i].es[j])%MOD;
rowData[next][i]=(rowData[next][i]+add)%MOD;
}
}
std::cout<<" ans="<<rowData[next][0];
point=(point+1)%2;
ans=rowData[next][0];
}
int now=turn%2;
int next=(turn+1)%2;
for(int i=0;i<LIMITER;i++){
dp[next][i].reset();
for(int j=0;j<LIMITER;j++){
if(dp[now][i].es[j]==0)continue;
dp[next][i].add_and_mult(dp[now][j],dp[now][i].es[j]);
}
}
turn++;
row/=2;
}
std::cout<<"\n lastAns="<<ans;
}

プロジェクトオイラー Problem 212 「結合直方体の体積」 †

Problem 212 「結合直方体の体積」 †

座標軸に平行な直方体 (axis-aligned cuboid) は {(x0, y0, z0), (dx, dy, dz)} で与えられ, x0 ≤ X ≤ x0 + dx, y0 ≤ Y ≤ y0 + dy, z0 ≤ Z ≤ z0 + dz, を満たす点で構成される. 直方体の体積は dx × dy × dzで求められる. 複数の直方体を結合したものの体積を考えた場合, 直方体に重なりがあれば, 結合直方体の体積は それぞれの直方体の体積の和より小さくなる.

C1, …, C50000 を以下のパラメータで与えられる座標軸に平行な直方体とする.

• x0 = S6n-5 modulo 10000
• y0 = S6n-4 modulo 10000
• z0 = S6n-3 modulo 10000
• dx = 1 + (S6n-2 modulo 399)
• dy = 1 + (S6n-1 modulo 399)
• dz = 1 + (S6n modulo 399)

S1,…,S300000 はラグ付きフィボナッチ法により生成される.

• 1 ≤ k ≤ 55 の場合, Sk = [100003 - 200003k + 300007k3] (modulo 1000000)
• 56 ≤ k の場合, [Sk-24 + Sk-55] (modulo 1000000)

したがって, C1 は {(7, 53, 183), (94, 369, 56)}, C2 は {(2383, 3563, 5079), (42, 212, 344)} となる

C1, …, C100 の結合直方体の体積は 723581599 である.

C1, …, C50000 の結合直方体の体積を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20212




解法
ＸＹ平面と平行な平面で直方体を切断し、断面の形の変化がない範囲を個別に計算しました。
最新のパソコンで36秒。
ちょっと遅いですがまあ解けただけでも良しという気分です。
正答者掲示板で他の方の回答を見てみました。
目から鱗な回答がいっぱいありますね。
jaapさんの解法がコンパクトでエレガント。
znezicさんの解法は魔法使いなみ。
どちらのコードもきちんと理解してみたい。
私のは我流で思いついた方法なのでもしかしたらほかの方の解法は一般的な解法なのかもしれません。
私はきっと井の中の蛙。


#include<stdio.h>
#include<set>
#include<map>
#include<iostream>
#include<time.h>
const int DELL=-1;
const int NEW=1;
const int ADD=1;

struct S{
     __int64 x,y;
     int zType,xyType,no;
     bool operator<(const S& s)const{
          if(x!=s.x)return x<s.x;
          if(y!=s.y)return y<s.y;
          if(xyType!=s.xyType)return xyType<s.xyType;
       
          return no<s.no;
     }
};

__int64 xyArea(std::set<S>& nowXYPoints,std::set<S>& points){
     std::set<S>::iterator it;
     S s1;
     for(it=nowXYPoints.begin();it!=nowXYPoints.end();it++){
          s1=(*it);
          if(s1.zType==DELL){
               points.erase(s1);
          }else{
               points.insert(s1);
          }
     }
   
     it=points.begin();
     if(it==points.end())return 0;
     int x=(*it).x;
   
     __int64 ysum,resultArea=0;
     int count;
   
     std::map<int,int> aliveY;
     std::map<int,int>::iterator yIt;
     std::set<int> dells;
     std::set<int>::iterator dellIt;
   
     while(it!=points.end()){
          __int64 dx;
          //std::cout<<"\nb";
          while(it!=points.end()){
               s1=(*it);
               if(x<s1.x)break;
               if(aliveY.find(s1.y)==aliveY.end())aliveY[s1.y]=0;
               aliveY[s1.y]+=s1.xyType;
               it++;
          }
          dx=s1.x-x;
          x=s1.x;
          dells.clear();
             
       
          for(yIt=aliveY.begin();yIt!=aliveY.end();yIt++){
               //std::cout<<(*yIt).first<<" "<<(*yIt).second<<")";
               if((*yIt).second==0)dells.insert((*yIt).first);
          }
          for(dellIt=dells.begin();dellIt!=dells.end();dellIt++){
               aliveY.erase((*dellIt));
          }
          yIt=aliveY.begin();
          if(yIt==aliveY.end())continue;
          int count=(*yIt).second;
          int oldY=(*yIt).first;
          __int64 sumY=0;
          for(yIt++;yIt!=aliveY.end();yIt++){
               count+=(*yIt).second;
               if(count==0){
                    sumY+=(*yIt).first-oldY;
                    yIt++;
                    if(yIt==aliveY.end()) break;
                    oldY=(*yIt).first;
                    count=(*yIt).second;
               }
          }
          resultArea+=(dx*sumY);
     }
     return resultArea;
}
const int LIMIT=6*50000;
const __int64 MOD=1000000;
const int MODXYZ=10000;
const int MOD_D=399;
std::map<int,std::set<S> > allPoints;
__int64 sk[LIMIT+1];

void append_point(int x,int y,int z,int xyType,int zType,int no){
     std::set<S> dammy;
     S s1;
     s1.xyType=xyType;
     s1.zType=zType;
     s1.x=x;
     s1.y=y;
     s1.no=no;
     if(allPoints.find(z)==allPoints.end())allPoints[z]=dammy;
     allPoints[z].insert(s1);
}

int main(){
   
     clock_t start,end;
       start = clock();
     for(__int64 k=1;k<=LIMIT;k++){
          if(k<=55){
               sk[(int)k]=(100003 - 200003*k + 300007*k*k*k)%MOD;
          }else{
               sk[(int)k]=(sk[(int)k-24]+sk[(int)k-55])%MOD;
          }
     }
     S s1;
     int x0,y0,z0,dx,dy,dz;
     for(int i=1;i<LIMIT;i+=6){
          x0=sk[i]%MODXYZ;
          y0=sk[i+1]%MODXYZ;
          z0=sk[i+2]%MODXYZ;
          dx=1+sk[i+3]%MOD_D;
          dy=1+sk[i+4]%MOD_D;
          dz=1+sk[i+5]%MOD_D;
          append_point(x0   ,y0   ,z0,ADD ,NEW,i);
          append_point(x0   ,y0+dy,z0,DELL,NEW,i);
          append_point(x0+dx,y0   ,z0,DELL,NEW,i);
          append_point(x0+dx,y0+dy,z0,ADD ,NEW,i);
       
          append_point(x0   ,y0   ,z0+dz,ADD ,DELL,i);
          append_point(x0   ,y0+dy,z0+dz,DELL,DELL,i);
          append_point(x0+dx,y0   ,z0+dz,DELL,DELL,i);
          append_point(x0+dx,y0+dy,z0+dz,ADD ,DELL,i);
     }
     __int64 ans=0,area,oldZ,t;
     std::map<int,std::set<S> >::iterator it;
     std::set<S> alivePoints;
     std::cout<<"a";
     it=allPoints.begin();
     area=xyArea((*it).second,alivePoints);
     oldZ=(*it).first;

     for(it++;it!=allPoints.end();it++){
          ans+=((*it).first-oldZ)*area;
          oldZ=(*it).first;
          area=xyArea((*it).second,alivePoints);
     }
     std::cout<<"ans="<<ans;
      end = clock();
       printf("\n%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
}

プロジェクトオイラー Problem 259 「到達可能数」 †

Problem 259 「到達可能数」 †

以下の規則に従った数式の答えとなるような正整数を到達可能と定義する:

1 から 9 の数字を, この順番でちょうど 1 度ずつ使う

連続した数字はつなげることができる(たとえば, 数字 2, 3, 4 を使って数字 234 が得られる)

4 つの2項演算(足し算, 引き算, 掛け算, 割り算)のみが許される

各演算は何度も使えるし, 一度も使われなくてもよい

単項のマイナスは使用できない

演算の順番を決めるために(入れ子でもよい)括弧を何度も使用してよい

例えば, (1/23) * ((4*5)-6) * (78-9) = 42 なので, 42 は到達可能である.

全ての到達可能な正整数の合計を求めよ.

正答者注(123456789も式として認められる)

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20259

解法

2分割しながら再帰で全探索し、計算は構造体Ｓを通して分数で計算してみたところ意外と少ない計算量で答えが出ました。

#include<stdio.h>

#include<set>

#include<iostream>

__int64 gcd ( __int64 a, __int64 b )

{

  __int64 c;

  while ( a != 0 ) {

     c = a; a = b%a;  b = c;

  }

  return b;

}

struct S{

     __int64 u,d;

     bool operator<(const S& s1)const{

          if(u!=s1.u)return u<s1.u;

          return d<s1.d;

     }

     void yakubun(){

          __int64 u1=u,d1=d;

          if(u1<0)u1=-u1;

          if(d1<0)d1=-d1;

          __int64 g=gcd(u1,d1);

          u=u/g;

          d=d/g;

          if(d<0){

               u=-u;

               d=-d;

          }

     }

     

     S add(const S& s1){

          S reS;

          reS.u=u*s1.d+s1.u*d;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S dell(const S& s1){

          S reS;

          reS.u=u*s1.d-s1.u*d;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S mult(const S& s1){

          S reS;

          reS.u=u*s1.u;

          reS.d=d*s1.d;

          reS.yakubun();

          return reS;

     }

     S div(const S& s1){

          S reS;

          reS.u=u*s1.d;

          reS.d=d*s1.u;

          reS.yakubun();

          return reS;

     }

};

S toNum(int L,int R){

     S s1;

     s1.d=1;

     s1.u=0;

     for(int i=L;i<=R;i++){

          s1.u=s1.u*10+i;

     }

     return s1;

}

std::set<S> saiki(int L,int R){

     std::set<S> results,Lset,Rset;

     std::set<S>::iterator itL,itR;

     results.insert(toNum(L,R));

     S s1,s2;

     for(int i=L;i<R;i++){

          Lset=saiki(L,i);

          Rset=saiki(i+1,R);

          for(itL=Lset.begin();itL!=Lset.end();itL++){

               s1=(*itL);

               if(s1.d==0)continue;

               for(itR=Rset.begin();itR!=Rset.end();itR++){

                    s2=(*itR);

                    if(s2.d!=0){

                         results.insert(s1.add(s2));

                         results.insert(s1.dell(s2));

                         results.insert(s1.mult(s2));

                    }

                    if(s2.u!=0){

                         results.insert(s1.div(s2));

                    }

               }

          }

     }

     return results;

}

int main(){

     std::set<S> ansSets=saiki(1,9);

     std::set<S>::iterator it;

     S s1;

     __int64 ans=0;

     

     for(it=ansSets.begin();it!=ansSets.end();it++){

          s1=(*it);

          if(s1.d==1&&s1.u>0){

               ans+=s1.u;

          }

     }

     std::cout<<"\nans="<<ans;

}

プロジェクトオイラー Problem 253 「お片づけ」 †

Problem 253 「お片づけ」 †

小さい子供が"数字イモムシ"を持っている. これは 40 のジグソーピースからなり, それぞれのピースは 1 つ数字が書いてあり, 一列につなげると 1 から 40 まで順番に並ぶ.

毎夜, 子供の父親は遊戯室にばらまかれたイモムシのピースを拾い集めなければならない. 父親は無作為にピースを拾っていき, 正しい順序に並べていく.
このようにイモムシを組み立てていくと, 徐々にくっついていっていくつかの断片が出来上がっていく.
断片の数は0(何もない状態)から始まり, だいたい 11 か 12 まで増えた後, やがてまた減っていき 1 (全部くっついた状態)で終わる.

例えば,

置かれたピース	現時点の断片
12	1
4	2
29	3
6	4
34	5
5	4
35	4
...	...

M を無作為にイモムシを片づける過程で起こった最大の断片の数とする.
10 ピースのイモムシの場合では, 各 M が起こる場合の数は

M	場合の数
1	512
2	250912
3	1815264
4	1418112
5	144000

つまり M の最頻値は 3 で平均値は 385643/113400 = 3.400732 である(小数点以下6桁に四捨五入).

40 ピースのイモムシの場合は M の最頻値は 11 である. では M の平均値は?

小数点以下6桁に四捨五入し回答せよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20253

解法
逆回しで40個そろった状態から一つずつ減らして分割していくと考えます。
lens[i]で長さiの断片がni個あると考えそこから減らしていきます。
１個の断片は断片が1個減ります。
2個の断片は左右どちらかが減ります。
3個以上の断片は左右どちらかが減るか二つの断片に分かれるかだけです。

減らすときできた組み合わせは残ってる全ピース数の多いほうから減らす形で計算します。

コード実行時間
3.08秒
平凡です。
もうちょっと早いコードを考えたいですね。

実はこのコード優先順位付きキューpqはいらずstd::setのaddS;もいりません。
全部std::mapのmemoだけで計算はできますが、わかりやすさを優先しました。



コード製作者　堀江伸一
兵庫県加古川市加古川町南備後



#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include <iomanip>
#include<time.h>

const int LIMIT=40;

struct S{
     //lens[1]は長さ１の断片がｎ1個ある
     //lens[2]は長さ２の断片がｎ2個ある
     int lens[LIMIT+1];
     int sum,split,splitMax;
   
     bool operator<(const S& s)const{
          if(sum!=s.sum)return sum<s.sum;
          if(split!=s.split)return split<s.split;
          if(splitMax!=s.splitMax)return splitMax<s.splitMax;
          for(int i=1;i<=LIMIT;i++){
               if(lens[i]!=s.lens[i])return lens[i]<s.lens[i];
          }
          return false;
     }
     void print(){
          printf("\n((inS sum=%d s=%d smax=%d)",sum,split,splitMax);
          for(int i=1;i<=LIMIT;i++){
               printf("%d",lens[i]);
          }
          printf(")\n");
     }
};

std::priority_queue<S> pq;
std::map<S,long double> memo;
std::set<S> addS;

void add_pq(S& s1){
     if(addS.find(s1)==addS.end()){
          addS.insert(s1);
          pq.push(s1);
     }
}

void split(S& s1){
     S s2;
     //まず分割してみる
   
     for(int i=1;i<=LIMIT;i++){
       
          if(i==1 && s1.lens[i]>0){
               //一個を分割しようとするので消える
               s2=s1;
               s2.sum--;
               s2.split--;
               s2.lens[i]--;
               if(memo.find(s2)==memo.end())memo[s2]=0;
               memo[s2]+=memo[s1]*s1.lens[i];
               add_pq(s2);
          }else if(i>2 && s1.lens[i]>0){
               //3個以上を分割しようとするので分割が一つ増える
             
               if(s2.split>s2.splitMax)s2.splitMax=s2.split;
               for(int j=1;j+1<i;j++){
                    s2=s1;
                    s2.sum--;
                    s2.lens[i]--;
                    s2.split++;
                    s2.lens[j]++;
                    s2.lens[i-j-1]++;
                    if(s2.splitMax<s2.split)s2.splitMax=s2.split;
                    if(memo.find(s2)==memo.end())memo[s2]=0;
                    memo[s2]+=memo[s1]*s1.lens[i];
                    add_pq(s2);
               }
          }
     }
     //分割数に変化がない場合の減らし方
     for(int i=2;i<=LIMIT;i++){
          s2=s1;
          s2.sum--;
          if(s1.lens[i]>0){
               s2.lens[i]--;
               s2.lens[i-1]++;
               if(memo.find(s2)==memo.end())memo[s2]=0;
               memo[s2]+=memo[s1]*s1.lens[i]*2;
               add_pq(s2);
          }
     }
}


int main(){
     clock_t start,end;
          start = clock();
   
     S s1;
   
     for(int i=0;i<=LIMIT;i++)s1.lens[i]=0;
     s1.sum=LIMIT;
     s1.splitMax=0;
     s1.split=0;
     s1.lens[LIMIT]=1;
   
     pq.push(s1);
     memo[s1]=1;
     long double anss[LIMIT+1]={0},all=0,ansSum=0;
   
     while(pq.empty()==false){
          s1=pq.top();
          pq.pop();
       
          if(s1.sum==1){
               anss[s1.splitMax+1]+=memo[s1];
          }else{
               split(s1);
          }
     }
     for(int i=0;i<=LIMIT;i++){
          std::cout<<"最大分割数"<<i<<"個"<<anss[i]<<"\n";
          all+=anss[i];
          ansSum+=anss[i]*i;
     }
     std::cout << std::setprecision(8);
     std::cout<<all<<" "<<ansSum<<" \nans="<<ansSum/all;
       
     end = clock();
     printf("\n%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
}

プロジェクトオイラー Problem 252 「凸ホール」 †

Problem 252 「凸ホール」 †

平面上に与えられた点の集合に対し, 以下を満たす凸多角形を凸ホール(convex hole)と定義する:
頂点は与えられた点のいくつかから成り, 内部に与えられた点を含まない(頂点以外に, 多角形の辺上に与えられた点があっても構わない)

例として, 下の図は 20 個の点とそれに対するいくつかの凸ホールを示している. 赤い多角形で示した凸ホールは 1049694.5 の単位正方形と面積が等しく, この点の集合に対し最大の凸ホールである.

この例では, 次の擬似乱数によって生成された 最初の 20 個の点 (T2k−1, T2k) (k = 1,2,…,20) を使用した.

S0 = 290797

Sn+1 = Sn2 mod 50515093

Tn = (Sn mod 2000 ) − 1000

すなわち, (527, 144), (−488, 732), (−454, −947), ... である.

この擬似乱数生成器による最初の 500 個の点を使用する凸ホールの中で, 最大の面積を求めよ.
小数点以下に1桁をつけて回答を入力せよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20252

解法
一分ルールは守れていません。
合格はしましたが手元の最新のパソコンで2分20秒も計算時間がかかっています。

点に0～499まで番号を付けており
コード実行するとその番号の点から始まる”とつ多角形”の検証が全部すんだら対応した数字が0から499まで表示されます。
最後に出てくる数字が答えとなる面積です。

スタートの点と2番目の点を決めて探索を始めます。
反時計回りで半開平面で片方にある点だけを選びながら探索を行います。
できるだけ大きな多角形になるように、折れ線の角度変化が小さいものから優先して探索し、
今いる点とその前の点の2セットが前に探索した状態よりも同じか小さな面積になってるなら探索を打ち切って別の探索へ向かいます。

それと始点を輪を作る中で一番番号の小さい点だと仮定して探索します。
ただし反時計回りでしか探索しないので二つ目の点のみ一つ目の点より小さな番号の点であるパターンを許容します。

これで少しだけ早くなります。
最新のパソコンで112.75秒。
まだまだ遅いです。
小手先のテクニックをいろいろきかしてみましたが対して効果が表れていません。
根本的な発想の転換が必要なようです。



#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<string.h>
#include<set>
#include<time.h>


const __int64 MOD_S=50515093;
const int POINT_SIZE=500;
std::vector<int> xs,ys;
std::set<int> alivePoints;

int dp[POINT_SIZE][POINT_SIZE];
int revDP[POINT_SIZE][POINT_SIZE];
struct S{
     int p1,p2,addArea;
     double r;
     bool operator<(const S& s)const{
          return r<s.r;
     }
};

int calc_area(int p1,int p2,int p3){
     int dx1,dy1,dx2,dy2;
     dx1=xs[p1]-xs[p3];
     dx2=xs[p2]-xs[p3];
   
     dy1=ys[p1]-ys[p3];
     dy2=ys[p2]-ys[p3];
     return dx1*dy2-dx2*dy1;
}

bool is_in_area(int start,int p2,int p3){
     std::set<int>::iterator it;
     for(it=alivePoints.begin();it!=alivePoints.end();it++){
          int i=(*it);
          if(i==start||i==p2||i==p3)continue;
          int r1=calc_area(start,p2,i);
          int r2=calc_area(p2,p3,i);
          int r3=calc_area(p3,start,i);
          if((r1>=0&&r2>=0&&r3>=0)||(r1<=0&&r2<=0&&r3<=0)){
               return true;
          }
     }
     return false;
}

int search(int start,int oldPoint,int nowPoint,int area){
     int resultArea=0;
     if(dp[nowPoint][start]<area){
          dp[nowPoint][start]=area;
     }
     std::priority_queue<S> pq;
     S s1;
     s1.p1=nowPoint;
     std::set<int>::iterator it;
     std::set<int> dells;
     int reAreaAdd=calc_area(start,oldPoint,nowPoint);

     for(it=alivePoints.begin();it!=alivePoints.end();it++){
          int i=(*it);
          if(i<start)continue;
          int aaa=calc_area(nowPoint,i,oldPoint);
          s1.addArea=calc_area(start,nowPoint,i);
          if((aaa<0)||s1.addArea<0||is_in_area(start,nowPoint,i)){
               dells.insert(i);
               continue;
          }
          s1.p2=i;
          double len1,len2;
          len1=hypot(xs[nowPoint]-xs[start],ys[nowPoint]-ys[start]);
          len2=hypot(xs[i]-xs[start],ys[i]-ys[start]);
          if(len1==0||len2==0)continue;
          int naiseki=(xs[i]-xs[nowPoint])*(xs[nowPoint]-xs[oldPoint]);
          naiseki+=(ys[i]-ys[nowPoint])*(ys[nowPoint]-ys[oldPoint]);

          s1.r=(1.0*naiseki)/(len1*len2);
          pq.push(s1);
     }
     for(it=dells.begin();it!=dells.end();it++){
          alivePoints.erase((*it));
     }
   
     while(pq.empty()==false){
          s1=pq.top();
          pq.pop();
          int area1=area+s1.addArea;
          if(dp[s1.p1][s1.p2]>=area1)continue;
          if(dp[s1.p1][s1.p2]==-1){
               dp[s1.p1][s1.p2]=area1;
               alivePoints.erase(s1.p2);
               int t=search(start, s1.p1, s1.p2,area1);
               if(resultArea<t){
                    resultArea=t;
               }
               alivePoints.insert(s1.p2);
          }else{
               dp[s1.p1][s1.p2]=area1;
               int t=revDP[s1.p1][s1.p2];
               if(resultArea<t){
                    resultArea=t;
               }
          }
     }
     alivePoints.insert(dells.begin(),dells.end());
     revDP[oldPoint][nowPoint]=resultArea+reAreaAdd;
     return resultArea+reAreaAdd;
}

void set_alive_points(int start,int second){
     alivePoints.clear();
     for(int i=0;i<POINT_SIZE;i++){
          if((i!=start) && (i!=second) && (calc_area(start,second,i)>0)){
               alivePoints.insert(i);
          }
     }
}

void search_w(){
     int ans=0;
     for(int i=0;i<POINT_SIZE;i++){
          printf("%d ",i);
          for(int j=0;j<POINT_SIZE;j++){
               if(i==j) continue;
               memset(dp,-1,sizeof(dp));
               memset(revDP,-1,sizeof(revDP));
               dp[i][j]=0;
               set_alive_points(i,j);
               int t=search(i,i,j,0);
               if(ans<t)ans=t;
          }
     }
     printf("%lf\n",ans/2.0);
}

int main(){
     __int64 Si=290797;
     clock_t start,end;
     start = clock();
     Si=(Si*Si)% MOD_S;
     for(int i=0;i<POINT_SIZE;i++){
          xs.push_back(Si%2000-1000);
          Si=(Si*Si)% MOD_S;
          ys.push_back(Si%2000-1000);
          Si=(Si*Si)%MOD_S;
     }
   
     search_w();
     end = clock();
       printf("%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
}