LeetCode 149. Max Points on a Line

LeetCode 149. Max Points on a Line
タイトルの説明
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
テーマ分析
平面上のn点の座標を与え,その中で最大何点が同じ直線上にあるかを求める.
まず複雑度の下限の解析を行う.まず2点から1本の線が構成されるので、一般的に直線数はn 2個に達する.少なくとも我々はこれらの直線を解析する必要があり、処理直線の複雑度をO(1)とすると、総複雑度は少なくともO(n 2)となる.
分析した後の考え方も明らかで、どのように各直線を処理する複雑さをできるだけ低減するかです.この問題では,1本の直線を処理することは,実際には現在の直線と他の直線が1本の直線上にあるかどうかを比較することである.それぞれの直線を「覚える」ことができ、1本の直線を処理するたびにその直線を対応する分類に加えることができれば、簡単になります.では、中学校時代に学んだことを思い出します.Ax+By+C=0は大まかに言えば、三元グループA,B,Cごとに唯一の直線を確定します.もちろんこの条件は十分ではありません.厳密に言えば、
2つの同じ直線ごとに、その方程式は必ず同じAx+By+C=0の形式に変換される.
このようにすれば、1つのmapで各直線が現れる数を記録するだけでよい.Line構造体は、それぞれの異なる直線を一意に識別する必要があり、上記の解析からLine構造体においてA, B, C三元群識別を利用すればよいことが分かる.
前述したように、A,B,Cを直接比較することは望ましくない.倍数関係があれば、事実上同じであるからだ.このような状況を回避するために、Line構造体を構築するたびに、まずその構築関数の中で以下の処理を行うことができる:1.A係数が負であれば、A,B,Cに−1を乗じて正係数に変換する.2.A,B,Cをgcd(A,gcd(B,C))で除算.この三元群に公因子がないことを確認します.
このように処理すると,処理後の各グループの異なるA,B,Cに対して異なる直線が対応していることが確認される.
一般的には、次の詳細なコードを示します.

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
inline int gcd(int a, int b) {
    int tmp, temp = a;
    if (a < 0) a*= -1;
    if (b < 0) b*= -1;
    if (a < b) swap(a, b); 
    while (b != 0) {
        tmp = b;
        b = a % b;
        a = tmp;
    }
    if (a != 0) return a;
    else return temp;
} 
inline void deal(int &A, int &B, int &C) {
    int tmp = gcd(A, gcd(B, C));
    if (tmp != 0) {
        A/= tmp;
        B/= tmp;
        C/= tmp;
    }

    if (A < 0 || (A == 0 && B < 0) || (A == 0 && B == 0 && C < 0)) {
        A*= -1;
        B*= -1;
        C*= -1;
        //      。
    }
}
struct Line{
    int A, B, C;
    Line() {

    }
    Line(int a, int b, int c) {
        A = a;
        B = b;
        C = c;
    }
    Line(Point &a, Point &b) {
        A = (a.y - b.y);
        B = (b.x - a.x);
        C = b.y * a.x - b.x * a.y;
        deal(A, B, C);
    }
    bool operator < (const Line &l)const
    {
        return (A < l.A || (A == l.A && B < l.B) || (A == l.A && B == l.B && C < l.C));
    }
};
class Solution {
public:
    int maxPoints(vector& points) {
        if (points.size() <= 1) return points.size();
        int max = 0, localmax = 0;
        for (int i = 0; i < points.size() - 1; ++i) {
            mapint> count;
            int overlap = 0;
            localmax = 0;
            for (int j = i + 1; j < points.size(); ++j) {
                Line temp(points[i], points[j]);
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    ++overlap;
                }
                else {
                    count[temp]++;
                }
                if (count[temp] > localmax) localmax = count[temp];

            }
            if (localmax + overlap > max) max = localmax + overlap;
        }
        cout << max << endl;
        return max + 1;
    }
};

その他の詳細

上の分析はアルゴリズムの大体の構想にすぎず、実際の過程では多くの詳細を処理しなければならない.例えばA=0の場合は、まずBの符号が一致していることなどを確認します.

上記の方法を用いても、n 2本の直線を直接処理することは望ましくない.このように重複点を処理できない場合があるからです.1本の直線を考慮すると、上の各点が何度も現れたので、どれだけ繰り返したのか正確に統計することはできません.

は起点分類処理に従うのが良い方法である.これにより、統計時に現在の点の重複点の数だけを漏算することが保証されますが、この値は私たちが処理できるときに変数で覚えることができます.上記のプログラムで採用されているのは、localmax， overlapがこれらの仕事をしていることです.

The End.