阿祁的部落格

ZeroJudge g220-華國探查 解題心得( 題目 )

解題概念:物件導向(OOP)

解題方法:首先我們要怎麼判斷很多點是否在同一條線上呢?用斜率?顯然不行，像是(0,0)、(1,10^9)、(1,10^9-1)顯然不是三點共線，但是以double型態計算斜率(定義斜率: Δ y/ Δ x)就很容易分不出來(因為兩個值都很小)，可是我們可以用另一種方式:先計算Δx、Δy除以GCD，然後以兩個互質的整數dx、dy表達斜率，在這裡為了利於分辨(像是+1 -1和-1 +1其實一樣)，我們使X恆正，也就是計算出來如果X為負就X、Y都乘上-1，這樣我們就可以判斷到底有沒有共線了!

再來我們實作一個物件dot，這個物件需要有以下性質:在new出一個新的物件時，它會自動連上所有之前的點，並且計算之間的斜率(這裡指的是dx、dy)，在連線的的物件中用Hashmap尋找(對應值記錄目前線連接到的數量L)，如果有找到就把線延長(先移除之前點的連線，在現在的這個dot上的Hashmap新增一個對應「斜率 - L+1」)，沒有則在現在的新增一個「斜率 - 2」的連線，另外我們利用一個陣列line[a]=b紀錄總共有b條線通過其中a個點(在連線時修改line的值)，最後計算結果就是 Σ (a>=4時的)線的數量line[a]x C(a,4) (排列組合數)，另外時間複雜度為O(n^2)。

註:下面map為了方便實作，我把斜率dx、dy綁成一個數，表示成dx*很大的數+dy

Java參考程式碼(有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2021/10/23

import java.io.*;

import java.util.*;

public class zjg220 {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static int ret,r;

    public static dot[] d;

    public static int[] line=new int[5000];

    public static void main(String[] args) throws Exception {

        final int n=rint();

        d=new dot[n];

        for(int i=0;i<n;i++) {

            d[i]=new dot(rint(),rint(),i);//新增點

        }

        long rt=line[4];

        long fac=1;

        for(int i=5;i<5000;i++) {

            fac=fac*i/(i-4);//排列組合

            rt+=fac*(long)line[i];

        }

        System.out.println(rt);

    }


    

    public static int rint() throws Exception {

        //輸入

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;


    }

}



class dot{

    int x,y;

    HashMap<Long,Integer> mp=new HashMap<>();

    dot(int a,int b,int c){

        int[] gcd=new int[2];

        int id,dx,dy;

        long m;//斜率

        Integer l;

        x=a;//點的座標

        y=b;

        for(int i=0;i<c;i++) {

            dx=this.x-zjg220.d[i].x;//差值

            dy=this.y-zjg220.d[i].y;

            gcd[0]=Math.abs(dx);

            gcd[1]=Math.abs(dy);

            id=0;

            if(gcd[0]!=0) {

                while(gcd[id^1]!=0) {

                    gcd[id]%=gcd[id^1];

                    id^=1;

                }

                dx/=gcd[id];//化成互質

                dy/=gcd[id];

                if(dx<0) {

                    dx*=-1;

                    dy*=-1;

                }

                m=2000000001L*dx+dy;//把斜率綁一起

            }

            else {

                m=1;//dx=0特例

            }

            l=zjg220.d[i].mp.get(m);//尋找有無斜率相同的線

            if(l==null) {

                mp.put(m,2);//新增線

            }

            else {

                mp.put(m,l+1);//線延長，點的數量+1

                zjg220.d[i].mp.remove(m);//移除舊線

                zjg220.line[l]--;//長度為L的線移除一條

                zjg220.line[l+1]++;//長度為L+1的線新增一條

            }

        }

    }

}