思路就是枚举两个三角形的顶点。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int x,y;
const int N=205;
int a[N][N],b[N][N];
int ans;
int dp[N][N];

void calc(){
	for(int j=1;j<=2*n-1;j+=2){
		dp[n][j]=1;
	}
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i*2-1;j+=2){
			dp[i][j]=1-a[i][j];
			if(dp[i][j]&&a[i+1][j]+a[i+1][j+1]+a[i+1][j+2]==0){
				dp[i][j]=min(dp[i+1][j],dp[i+1][j+2])+1;
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		a[x][y]=1;
	}
	calc();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=2*i-1;j++){
			for(int a=i;a<=n;a++){
				for(int b=(a==i?j:1);b<=2*a-1;b++){
					if(i==a&&j==b) continue;
					int &p=dp[i][j],&q=dp[a][b];
					if(i==a){
						int mx=b-j;
						mx/=2;
						if(max(p,q)>mx){
							ans=max(ans,max(p,q)*max(p,q)+min(mx,min(p,q))*min(mx,min(p,q)) );
						}
						else ans=max(ans,p*p+q*q);
					}
					else{
						int mx=max(i,a)-min(i,a);
						ans=max(ans,min(mx,p)*min(mx,p)+q*q);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
}