Untitled
raw download clone
C
views 25
,
size 1908 b
#include<stdio.h>

int N,flag=0;
long Ax[102][102],Ay[102][102];
int valid[102][102];

void next_pt(int num1,int num2)
{
     valid[num1][num2]=1;
     for(int i=1;i<=N-num2;i++)
     {
          if(Ax[num1][num2]*Ay[num1][num2+i]==Ay[num1][num2]*Ax[num1][num2+i])//交叉相乘會相等
          {
               flag=1;
               valid[num2][num2+i]=1;//兩兩相連即令1
               valid[num1][num2+i]=1;
               next_pt(num1,num2+i);//讓他亂跑遍同一條線的點
               next_pt(num2,num2+i);
          }
     }
}

int main(void)
{
     int T,count=0;
     long x[102],y[102];

     //slope==Ay/Ax

     scanf("%d",&T);
     while(T--)
     {
          scanf("%d",&N);
          for(int i=1;i<=N;i++)
          {
               scanf("%ld%ld",&x[i],&y[i]);
          }
          for(int i=1;i<=N;i++)
          {
               for(int j=1;j<=N-i;j++)//X、Y變化量
               {
                    Ax[i][i+j]=x[i]-x[i+j];
                    Ay[i][i+j]=y[i]-y[i+j];
               }
          }
          for(int i=1;i<=N;i++)
          {
               for(int j=1;j<=N-i;j++)
               {
                    if(valid[i][i+j]==0)
                    {
                         next_pt(i,i+j);
                         //printf("%d,%d\n",i,i+j);
                    }
                    //找是否被連過再決定要不要進入尋找下個點
                    if(flag)//有發現第三個點
                    {
                         count++;
                    }
                    flag=0;
               }
          }
          printf("%d\n",count);
          count=0;//歸零
          for(int i=1;i<=N;i++)
          {
               for(int j=1;j<=N-i;j++)
               {
                    valid[i][i+j]=0;
               }
          }

     }
     return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.