Posted on 2014-01-11 01:54
Uriel 閱讀(127)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode
這題POJ上有原題，平面上一堆點(diǎn)，求最多共線點(diǎn)數(shù)，方法不難，1~n枚舉所有點(diǎn)，求它和其他點(diǎn)分別構(gòu)成直線的斜率，然后sort，然后算有幾個(gè)相同斜率的，求個(gè)max
這題的trick在于有重復(fù)點(diǎn)，為了處理這個(gè)搞了半天【我太挫...然后用的是很Naive的辦法，重復(fù)點(diǎn)單獨(dú)計(jì)數(shù)單獨(dú)算，另外斜率不存在的時(shí)候設(shè)為一個(gè)很大的數(shù)（1e10）
1 /**
2 * Definition for a point.
3 * struct Point {
4 * int x;
5 * int y;
6 * Point() : x(0), y(0) {}
7 * Point(int a, int b) : x(a), y(b) {}
8 * };
9 */10 class Solution {
11 public:
12 struct pt{
13 double k;
14 int fg;
15 bool operator<(
const pt &m)
const {
16 return k < m.k;
17 }
18 }pp[1010];
19 int maxPoints(vector<Point> &points) {
20 int max = 0, pre_max = 0;
21 int cnt = points.size();
22 for(
int i = 0; i < cnt; ++i) {
23 int nt = 0, nnt = 0;
24 for(
int j = i; j < cnt; ++j) {
25 if((points[j].x - points[i].x) < -1e-6 || (points[j].x - points[i].x) > 1e-6) {
26 pp[j].k = (
double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
27 pp[j].fg = 0;
28 }
29 else if((points[j].x - points[i].x) > -1e-6 && (points[j].x - points[i].x) < 1e-6 && (points[j].y - points[i].y) > -1e-6 && (points[j].y - points[i].y) < 1e-6) {
30 pp[j].fg = 1;
31 nnt++;
32 }
33 else {
34 pp[j].k = 1e10;
35 pp[j].fg = 0;
36 }
37 }
38 sort(pp + i + 1, pp + cnt);
39 for(
int j = i + 2; j < cnt; ++j) {
40 if(pp[j].fg)
continue;
41 else {
42 if(!nt) nt = 1;
43 if(pp[j - 1].k == pp[j].k) nt++;
44 else {
45 if(nt + nnt> max) max = nt + nnt;
46 nt = 1;
47 }
48 }
49 }
50 if(nt + nnt> max) max = nt + nnt;
51 if(nnt < cnt - i && nnt + 1 > max) max = nnt + 1;
52 }
53 if(cnt > 2)
54 return max;
55 else56 return cnt;
57 }
58 };