## What is Python's isinstance called in golang?

Starlight_ Glimmer 2020-11-17 21:08:09
python isinstance golang

#### Brief introduction

Find the number of unordered triples with the same Manhattan distance between any two points .

#### title

##### Step.1

First , There is a conclusion ： On the plane to the point $$(x,y)$$ The Manhattan distance is $$d$$ The trajectory of the point , In order to $$(x,y)$$ Centered ,$$2d$$ For the diagonal square .（ It's the quadrilateral in the graph $$BCDE$$

This should look better , When the dot is sliding on a square , Ordinate $$±1$$, The abscissa is also $$±1$$. To be more exact , Abscissa $$A$$ far $$1$$, The ordinate is away from $$A$$ near $$1$$, Abscissa $$A$$ near $$1$$, The ordinate is away from $$A$$ far $$1$$. But the diamond is oblique , Not easy to do , So let's spin ,“ right ”, hold $$(x,y)$$ become $$(x+y,x-y)$$.

This is probably why many of the solutions are saying that it can be transformed into Chebyshev distance .

##### Step.2

Another conclusion ：$$(x,y)$$ Transform the coordinate system $$->(x+y,x-y)$$, Manhattan distance in the original coordinate system = Chebyshev distance in the new coordinate system

Just a quick explanation ：

At two o 'clock $$(x1,y1),(x2,y2)$$

Manhattan distance in the original coordinate system $$=|x1-x2|+|y1-y2|$$

Chebyshev distance in the new coordinate system $$=max(|x1+y1-x2-y2|,|x1-y1-x2+y2|)=max(|x1-x2+y1-y2|,|x1-x2-(y1-y2)|)$$

Let's talk about it $$x1-x2$$ and $$y1-y2$$ The sign and absolute value of the .

Make $$x1-x2=m,y1-y2=n$$（ It's easy to write

$$m,n$$ Same number ,$$|m+n|=|m|+|n|,|m-n|=||m|-|n||$$

be aware , No matter what $$|m|,|n|$$ How about the size relationship ,$$|m-n|=(|m|-|n|)/(|n|-|m|)$$ It's all smaller than $$|m|+|n|$$ Of , Obtain evidence .

$$m,n$$ When there is a different sign ,$$|m+n|=||m|-|n||,|m-n|=|m|+|n|$$, Empathy .

Another similar conclusion , I also add here （ This problem doesn't use ）：$$(x,y)->(\frac{x+y}2,\frac{x-y}2)$$, Chebyshev distance of the original coordinates = Manhattan distance in new coordinates , Prove the same .

Of course , It's an algebraic way of understanding , I think it can be simpler in terms of Geometry .

It was said that , Square $$BCDE$$ Is to meet the Manhattan distance for $$d$$ Track of .

So if you put the trajectory right , Put every point on the square according to $$(x,y)->(x+y,x-y)$$ mapping （ Transform the coordinate system ）, Draw one to $$2d$$ For a square with a side length , And by geometric relations （ Look at the picture ） Easy to know , This square is to $$A$$ Point Chebyshev distance is $$d$$ The trajectory of the point .

##### Step.3

A conditional triple must have two dots $$x$$ or $$y$$ The coordinates are the same .

If you first select two points that do not meet the above requirements $$A,B$$ It's marked out in the picture $$T,U$$ It's the third eligible person spot , They all satisfy the above conditions .($$A$$ The point that meets the condition is with $$A$$ The side length of the center is $$3$$ The square of ,$$B$$ Empathy , So the point satisfying the condition is the intersection of two square trajectories )（ I'm a little bit messy ##### Step.4

that , The qualified Sanyuan Group leader looks like this ： All the whole points on the line meet the conditions .

You can enumerate $$A,B$$ spot , because $$A,B$$ Of $$x/y$$ The coordinates are the same , The complexity is $$O(n^3)$$ Of , As for the calculation $$CD$$ How many dots between , This can be prefixed and maintained .

$$x,y$$ The coordinates are the same , however $$ABC,BCD,ABD,BDA$$ It's going to be counted twice （ That is, the boundary points will be calculated repeatedly ）, So in the second enumeration , It's OK not to include the boundary points .

##### Step.5

In fact, there is no need to transform the coordinate system , It's OK to take the original oblique coordinates directly , It's just a little more troublesome to write about , And it's going to rotate in four directions , But you don't have to think about the middle deduction .

But if you've seen something like this , It will be much more convenient to do questions .

#### ►Code View

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
#define N 305
#define DEL 100000
#define INF 0x3f3f3f3f
int rd()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48); c=getchar();}
return f*x;
}
int n,ans;
char mp[N][N];
int a[N<<1][N<<1],s1[N<<1][N<<1],s2[N<<1][N<<1];
int main()
{
n=rd();
for(int i=1;i<=n;i++)
{
scanf("%s",mp[i]+1);
for(int j=1;j<=n;j++)
if(mp[i][j]=='*')
a[i+j][i-j+n]=1;// To Chebyshev distance Prevent negative numbers Translation coordinates
}
n*=2;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s1[i][j]=a[i][j]+s1[i][j-1],s2[i][j]=a[i][j]+s2[i-1][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j])// The first cow spot
for(int k=j+1;k<=n;k++)// The second cow spot And the first point i identical
if(a[i][k])
{
int d=i+(k-j);
if(d<=n) ans+=s1[d][k]-s1[d][j-1];
d=i-(k-j);
if(d>=1) ans+=s1[d][k]-s1[d][j-1];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[j][i])
for(int k=j+1;k<=n;k++)
if(a[k][i])
{
int d=i+(k-j);
if(d<=n) ans+=s2[k-1][d]-s2[j][d];// We need to dig out the boundary points It's been calculated before
d=i-(k-j);
if(d>=1) ans+=s2[k-1][d]-s2[j][d];
}
printf("%d\n",ans);
return 0;
}