D****6
发帖数: 278 | 1 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？ |
z****e
发帖数: 54598 | |
l*n
发帖数: 529 | 3 没有，不是dp，就是cc150的题。
【在 z****e 的大作中提到】
: 看题目就感觉要dp了
|
s********u
发帖数: 1109 | 4 struct Line{
double slope;
double intercept;
Line(Point p, Point q){
if(p.x == q.x){
slope = numeric_limits::max();
intercept = p.x;
}else{
slope = (double)(p.y - q.y)/(double)(p.x - q.x);
intercept = p.y - slope * p.x;
}
}
};
struct Comp{
static double eps;
bool operator()( const Line &l1, const Line &l2){
if( l1.slope - l2.slope < -eps )
return true;
if( l1.slope - l2.slope > eps)
return false;
return (l1.intercept - l2.intercept < -eps);
}
};
double Comp::eps = 0.000000001;
bool fitLine(const Point& p,const Line &line){
if( abs(line.slope - numeric_limits::max()) < 0.000000001 )
return p.x == (int)line.intercept;
return abs(p.x * line.slope + line.intercept - p.y) < 0.000000001;
}
class Solution {
public:
int maxPoints(vector &points) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(points.empty()) return 0;
map table;
for(int i = 0; i < points.size(); i++)
for(int j = i+1; j < points.size();j++){
Line local(points[i],points[j]);
table[local]++;
}
int maxcnt = 1;
auto maxLine = table.begin();
for(auto it = table.begin(); it != table.end(); ++it )
if( it->second > maxcnt){
maxcnt = it->second;
maxLine = it;
}
maxcnt = 0;
for(int i = 0; i < points.size();i++){
if(fitLine(points[i],maxLine->first) )
maxcnt++;
}
return maxcnt;
}
}; |
h*********o
发帖数: 230 | 5 不要用slope 跟hashmap 做。。。耗了好多时间
用三点共线
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
|
s********u
发帖数: 1109 | 6 我是找到那条线，然后再扫一遍，看在这条线上有多少个点。否则的话，比如单一个点
，就没法解决。因为有无限种可能。
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
|
w*******s
发帖数: 96 | 7 牛人，居然用double的方法做出来了。能解释一下比较函数和思路吗？先找平行线？然
后看点是不是在那个上面？
struct Comp{
static double eps;
bool operator()( const Line &l1, const Line &l2){
if( l1.slope - l2.slope < -eps )
return true;
if( l1.slope - l2.slope > eps)
return false;
return (l1.intercept - l2.intercept < -eps);
}
}; |
l*n
发帖数: 529 | 8 我写的，利用输入为int，就拿dx & dy来标示直线了。
public int maxPoints(Point[] points) {
assert(points!=null);
if (points.length<2) return points.length;
int globalMax=0;
for (int i=0; i
Point curr=points[i];
int max=0, repeat=1;
Map map=new HashMap();
for (int j=i+1; j
Point other=points[j];
String b=null;
if (other.x==curr.x) {
if (other.y==curr.y) {
repeat++;
continue;
}
b=String.valueOf(Integer.MAX_VALUE);
} else if (other.y==curr.y) {
b=String.valueOf(0);
} else {
int gcd=gcd(other.y-curr.y, other.x-curr.x);
b=String.valueOf((other.y-curr.y)/gcd)+','+
String.valueOf((other.x-curr.x)/gcd);
}
if (!map.containsKey(b)) {
map.put(b, 1);
} else {
map.put(b, map.get(b)+1);
}
if (map.get(b)>max) max=map.get(b);
}
if (max+repeat>globalMax) globalMax=max+repeat;
}
return globalMax;
}
int gcd(int a, int b) {
return b==0?a:gcd(b, a%b);
}
【在 s********u 的大作中提到】
: struct Line{
:
: double slope;
: double intercept;
:
:
: Line(Point p, Point q){
:
: if(p.x == q.x){
: slope = numeric_limits::max();
|
s********u
发帖数: 1109 | 9 就是优先看斜率，再看截距。比较函数要注意严格弱序。只要定义了严格弱序，那么“
=”就相当于 非'a
我本来想用系统自带的epsilon，但可能太小了，反而失败了。就随便设了0.000001
【在 w*******s 的大作中提到】
: 牛人，居然用double的方法做出来了。能解释一下比较函数和思路吗？先找平行线？然
: 后看点是不是在那个上面？
: struct Comp{
:
: static double eps;
:
: bool operator()( const Line &l1, const Line &l2){
:
: if( l1.slope - l2.slope < -eps )
: return true;
|
m**********4
发帖数: 774 | 10 我们可以DEFINE一条线，用Y＝KX＋B， K和B 确定了Y就确定了。对于每个点，算其他
点跟它的线的K和B（中学代数，但要考虑K＝无穷大的情况）。建立一个MAP，用K和B做
KEY。但问题是K和B都是DOUBLE怎么办呢？DOUBLE可以转换成INTVALUE，然后对素数求
模来计算HASHVALUE。用这条线的COUNT做VALUE。输出最大的那个就可以。这题还有一
个EDGE CASE 是如果有几个点都一样怎么办。
已经算过的点不能再算。所以我们LOOP的时候，
for (int i = 0; i < points.length; ++i)
for (int j = i+1; j < points.length; ++j)
底下有朋友贴了CODE我觉得不错。
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
|
|
|
d**********x
发帖数: 4083 | 11 k & b should not be expressed in double. just use number pairs.
they are rational numbers in this problem
且好
【在 m**********4 的大作中提到】
: 我们可以DEFINE一条线，用Y＝KX＋B， K和B 确定了Y就确定了。对于每个点，算其他
: 点跟它的线的K和B（中学代数，但要考虑K＝无穷大的情况）。建立一个MAP，用K和B做
: KEY。但问题是K和B都是DOUBLE怎么办呢？DOUBLE可以转换成INTVALUE，然后对素数求
: 模来计算HASHVALUE。用这条线的COUNT做VALUE。输出最大的那个就可以。这题还有一
: 个EDGE CASE 是如果有几个点都一样怎么办。
: 已经算过的点不能再算。所以我们LOOP的时候，
: for (int i = 0; i < points.length; ++i)
: for (int j = i+1; j < points.length; ++j)
: 底下有朋友贴了CODE我觉得不错。
|
m**********4
发帖数: 774 | 12 You should be able to use doubles. Need to rewrite equals and hashcode
though. At least it is OK to pass OJ.
【在 d**********x 的大作中提到】
: k & b should not be expressed in double. just use number pairs.
: they are rational numbers in this problem
:
: 且好
|
D***0
发帖数: 138 | 13 不明白同一个点应该算两次？
Input: [(0,0),(0,0)]
Output: 1
Expected: 2 |
s*****p
发帖数: 108 | 14 重复的点肯定共线，所以都要算进去。
【在 D***0 的大作中提到】
: 不明白同一个点应该算两次？
: Input: [(0,0),(0,0)]
: Output: 1
: Expected: 2
|
D***0
发帖数: 138 | 15 我理解重复的点就算是一个点了，虽然在输入里给的是两个点，但是在坐标系里就是一
个点
【在 s*****p 的大作中提到】
: 重复的点肯定共线，所以都要算进去。
|
l****3
发帖数: 17 | 16 斜率这里可以用分数来表示，所有的斜率都化成最简分数，这样就不怕精度了 |
q****m
发帖数: 177 | 17 我的这个为什么超时了呢？ 斜率我用一对整数(x, y)表示,而且让 x>= 0.斜率（0，y
）比其他的斜率都大。斜率(x1, y1) 比(x2, y2) 小的话意味着
y1/x1 < y2/x2, 转化成等价的形式 y1 * x2 < y2 * x1
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
static bool compare(const Point &a, const Point &b)
{
if(b.x == 0)
{
return true;
}
return a.y * b.x < a.x * b.y;
}
int maxPoints(vector &points) {
int cur = 0;
if(points.size() <= 2)
{
return points.size();
}
for(int i = 0; i < points.size() - 1; ++i)
{
vector v;
for(int j = i+ 1; j < points.size(); ++j)
{
Point tmp = Point(points[j].x - points[i].x, points[j].y -
points[i].y);
if(tmp.x < 0)
{
tmp.x = -tmp.x;
tmp.y = -tmp.y;
}
v.push_back(tmp);
}
sort(v.begin(), v.end(), compare);
for(int j = 0; j < v.size(); ++j)
{
int start = j;
while(start < v.size() && v[j].y * v[start].x == v[j].x * v[
start].y)
{
start ++;
}
cur = max(cur, start - j);
j = start - 1;
}
}
return cur + 1;
}
};
【在 l*n 的大作中提到】
: 我写的，利用输入为int，就拿dx & dy来标示直线了。
: public int maxPoints(Point[] points) {
: assert(points!=null);
: if (points.length<2) return points.length;
: int globalMax=0;
: for (int i=0; i: Point curr=points[i];
: int max=0, repeat=1;
: Map map=new HashMap();
: for (int j=i+1; j
|
