「题解」直角三角形

(未完待续:题目,题解ACD,题解B代码)

题目链接:GMOJ 1385

题目

题目描述

输入格式

输出格式

样例输入输出

#1

  • Input:
3
4 2
2 1
1 3
  • Output:
1

#2

  • Input:
4
5 0
2 6
8 6
5 7
  • Output:
0

#3

  • Input:
5
-1 1
-1 0
0 0
1 0
1 1
  • Output:
7

数据范围

时空限制

本题目有多种解法(直接模拟,三种正解)。

题解

解法 A(直接模拟)

思路

直接模拟的方法比较显然,判断直角三角形我们使用勾股定理即可。

代码

解法 B(正解)

思路

代码

时间复杂度为 $\Theta(n^2\log _ 2n)$,预计得分 $100$ 分。

#include<cstdio>
#include<algorithm>
using std::pair;
#include<map>
using std::map;
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;//读入优化的变量
inline int read(void){//输入函数
    register bool flag=false;
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch){
        if(ch=='-')
            flag=true;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return flag?-res:res;
}
const int MAXN=1500+5;
struct Node{//节点
    int x,y;
    void Read(void){
        x=read(),y=read();
        //scanf("%d%d",&x,&y);
        return;
    }
};
int n;
Node a[MAXN];
map<ll,pair<int,int>/**/> M;
int gcd(int,int);
ll Zip(int,int);
int main(void){
    register int i,j;
    register int zx,zy,dx,dy,G;
    register ll ans=0;
    map<ll,pair<int,int>/**/>::iterator it;
    n=read();
    //scanf("%d",&n);
    for(i=1;i<=n;++i)
        a[i].Read();
    for(i=1;i<=n;++i){
        zx=zy=0;
        M.clear();
        for(j=1;j<=n;++j){
            if(i==j)
                continue;
            dx=a[i].x-a[j].x;
            dy=a[i].y-a[j].y;
            if(dx==0)
                ++zy;
            else if(dy==0)
                ++zx;
            else{
                G=gcd(dx,dy);
                dx/=G;
                dy/=G;
                if(dx<0&&dy<0)
                    dx=-dx,dy=-dy;//3->1
                if(dx<0||dy<0){
                    if(dx<0)
                        dx=-dx;
                    else
                        dy=-dy;
                    ++M[Zip(dy,dx)].second;
                }
                else{
                    ++M[Zip(dx,dy)].first;
                }
            }
        }
        ans+=(ll)zx*zy;
        for(it=M.begin();it!=M.end();++it){
            ans+=(ll)(it->second.first)*(ll)(it->second.second);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
ll Zip(int x,int y){
    return (((ll)x)<<32)|y;
}