#!/bin/sh
f=/tmp/a$$
cat >$f.cpp <<'EOF'
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <chrono>
using namespace std;
int main(){
const int W=140,H=110,N=W*H,P=29*23,K=11;
vector<pair<int,int>> pos;for(int y=0;y<=H;y+=5)for(int x=0;x<=W;x+=5)pos.push_back({x,y});
vector<vector<int>> pix(P);for(int q=0;q<P;q++){auto [x,y]=pos[q];for(int j=0;j<H;j++)for(int i=0;i<W;i++)if((i+.5-x)*(i+.5-x)+(j+.5-y)*(j+.5-y)<=400)pix[q].push_back(j*W+i);}
mt19937 g(1234567);vector<int> bestS;int best=0;auto start=chrono::steady_clock::now();
for(int rep=0;;rep++){
if(chrono::duration<double>(chrono::steady_clock::now()-start).count()>5.5)break;
vector<int> s;vector<short> cnt(N,0);int val=0;
for(int k=0;k<K;k++){vector<pair<int,int>> cand;cand.reserve(P);for(int q=0;q<P;q++){int gain=0;for(int z:pix[q])gain+=cnt[z]==0;cand.push_back({gain,q});}sort(cand.begin(),cand.end());int pool=rep==0?1:40;uniform_int_distribution<int> dd(0,pool-1);int q=cand[P-1-dd(g)].second;s.push_back(q);for(int z:pix[q]){if(cnt[z]++==0)val++;}}
uniform_real_distribution<double> U(0,1);uniform_int_distribution<int> SI(0,K-1),QI(0,P-1);
for(int it=0;it<15000;it++){int a=SI(g),old=s[a],q=QI(g);if(q==old)continue;int nv=val;for(int z:pix[old])if(--cnt[z]==0)nv--;for(int z:pix[q])if(cnt[z]++==0)nv++;double T=80.0*(1.0-it/15000.0)+.2;if(nv>=val||U(g)<exp((nv-val)/T)){s[a]=q;val=nv;}else{for(int z:pix[q])cnt[z]--;for(int z:pix[old])cnt[z]++;}}
bool imp=true;while(imp){imp=false;for(int a=0;a<K;a++){int old=s[a],base=val;for(int z:pix[old])if(--cnt[z]==0)base--;int bq=old,bv=val;for(int q=0;q<P;q++){int v=base;for(int z:pix[q])v+=cnt[z]==0;if(v>bv)bv=v,bq=q;}for(int z:pix[bq])cnt[z]++;s[a]=bq;if(bv>val)val=bv,imp=true;}}
if(val>best){best=val;bestS=s;cerr<<"new "<<best<<" rep "<<rep<<"\n";}
}
cout<<"BEST "<<best<<" "<<(double)best/N<<"\n";for(int q:bestS)cout<<pos[q].first<<","<<pos[q].second<<" ";cout<<"\n";}
EOF
clang++ -std=c++17 -O3 $f.cpp -o $f && $f
rm -f $f $f.cpp