Untitled
raw download clone
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
*/
close fullscreen
Login or Register to edit or fork this paste. It's free.