Untitled
C
views 20
,
size 2463 b
``````#include<stdio.h>
//#define Input

int main(void){
int T,N;
int x[105];
int y[105];   // (x[i],y[i])
int col[105][105];
int temp[105];
int c=0,tmp_c=0;
int dx,dy;
#ifdef Input
freopen("11619_sampleIn.txt","r",stdin);
#endif // Input
scanf("%d",&T);
while(T--){
c=0;
for(int i=0;i<105;i++)
for(int j=0;j<105;j++)
col[i][j] = 0;

scanf("%d",&N);
for(int i = 1; i<=N ;i++)
scanf("%d %d",&x[i],&y[i]);

for(int i = 1; i<=N ; i++){
for(int j = i+1 ; j<=N ; j++){
if(col[i][j] != 0)//i,j共線過則點2跳下一個
continue;
dx = x[j] - x[i];
dy = y[j] - y[i];
tmp_c = 0;

for(int k = j+1 ; k<=N ; k++){
if( col[i][j] == 0 && (dx * (y[k]-y[i]) == dy * (x[k]-x[i])) ){//i,j未共線過 , 點k符合i,j線的公式
c++;//編號+1
col[i][j] = c;
col[i][k] = c;
col[j][k] = c;
temp[tmp_c] = k;//點k放入暫存
tmp_c++;//暫存數+1
}else if(dx * (y[k]-y[i]) == dy * (x[k]-x[i])){//i,j共線過了
col[i][k] = c;
col[j][k] = c;
temp[tmp_c] = k;
tmp_c++;
}
}
if(tmp_c>1){//i,j以外的點紀錄共線
for(int k=0 ; k<tmp_c; k++)
for(int l=k+1; l<tmp_c ; l++)
col[ temp[k] ][ temp[l] ]= c;
}

}
}

printf("%d\n",c);
}

}
/*
設一個 col[點1][點2] 紀錄共線
tmp_c 紀錄點1,2外的共線點的數量
temp[tmp_c]暫存點1,2外共線的點

EX: 6個點 {1,2,3,6}共線1號 {4,5,6}共線2號
col[1][2] = 1, col[1][3] = 1, col[3][6]=1
col[4][5] = 2, col[4][6] = 2,

i For I i~n 選點1
j For II i+1~n 選點2
k For III i+2 ~ n 確認點3是否共線
For III-2,IV (a:a~tmp_c,b:a+1~tmp_c) 點1,2外的點紀錄共線編號
ex: i=1,j=2 k=3,6共線
temp[0] = 3 , temp[1] = 6
III-2,IV : col[temp[a]][temp[b]] = col[3][6] = 1
*/``````