直角三角形 (Standard IO)-白红宇

直角三角形 (Standard IO)

阅读量：4583 次

发布时间：2019-06-09

本文共 1685 字，大约阅读时间需要 5 分钟。

题意/Description:

二维平面坐标系中有N个点。

从N个点选择3个点，问有多少选法使得这3个点形成直角三角形。

读入/Input：

第一行包含一个整数N(3<=N<=1500)，表示点数。

接下来N行，每行包含两个用空格隔开的整数表示每个点的坐标，坐标值在-10^9到10^9之间。

每个点位置互不相同。

输出/Output：

输出直角三角形的数量。

题解/solution：

要看完，题解在后头。

今天的题目都好难，而我作为pascal的忠诚粉丝，转为c++的初学者，真要吐槽几句。c++挺方便的，至少不用打sort（快排），可却忘了不稳定着一东东，带着悲催的又烦闷的心情打归并。归并吗，也不难。可我昨天硬是用c++打难题，调了两个小时的空气。完后，怎么还错。调了半个小时的空气，一个奇怪的东西。

c++的数组是从0开始的！！！

然后果断AC啦，“哈哈哈，AC啦！“。我记录下了着神圣的、有历史意义的一刻：

着对于一个c++的初级粉丝是一个巨大的surprised啊。感谢大家看到这了，进入正题8。

-----------------------------------------------我是可爱又可恨的分割线-----------------------------------------

首先，枚举两个点，就是一次函数y=k'x+b，那么与它垂直的线就是y=k''x+b（别在意格式），你会发现k'和k''是互为负倒数（怎么发现的？脑补）。那么怎么求一次函数呢？斜率优化，不懂的问度娘，脑补脑补。然后去看看lxf的。看看时间也不早了，我先。

代码/Code：

#include 
    
         #include 
     
          #include 
      
           #include 
       
            #include 
        
             #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 using namespace std;struct arr{ long long x,y; int cover;}tu[1505],f[1505];int ans[5];int x[1505],y[1505];int n,sum;int cmp(arr a,arr b){ return a.x*b.y>a.y*b.x;}int rt90(int o){ long long t; t=tu[o].x; tu[o].x=tu[o].y; tu[o].y=-t; tu[o].cover+=1; tu[o].cover%=4;}int merge(int x,int y){ if (x!=y){ int mid=(x+y)/2; merge(x,mid); merge(mid+1,y); //memset(f,0,sizeof(f)); int i=x,k=x; int j=mid+1; while (i<=mid&&j<=y){ if (tu[i].y*tu[j].x
                 
                  0)&&(tu[j].y>=0))) rt90(j); } merge(2,n); int j=2; while (j<=n){ memset(ans,0,sizeof(ans)); int k=j; while ((k<=n)&&(tu[j].y*tu[k].x==tu[j].x*tu[k].y)){ ans[tu[k].cover]+=1; k+=1; } j=k; for (int o=0;o<=3;o++) sum+=ans[o]*ans[(o+1)%4]; } } printf("%ld",sum);}

转载于:https://www.cnblogs.com/zyx-crying/p/9319658.html

你可能感兴趣的文章