三哥也有行动派！（视频） (转载)# Joke - 肚皮舞运动
D*6
1 楼
这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
m*c
2 楼
【 以下文字转载自 Military 讨论区 】
发信人: changbaihou (秋裤外穿), 信区: Military
标 题: 三哥也有行动派！（视频）
发信站: BBS 未名空间站 (Fri Aug 30 23:16:15 2013, 美东)
发信人: changbaihou (秋裤外穿), 信区: Military
标 题: 三哥也有行动派！（视频）
发信站: BBS 未名空间站 (Fri Aug 30 23:16:15 2013, 美东)
z*e
3 楼
看题目就感觉要dp了
H*g
4 楼
没ppt就失败了
l*n
5 楼
没有，不是dp，就是cc150的题。
【在 z****e 的大作中提到】
: 看题目就感觉要dp了
【在 z****e 的大作中提到】
: 看题目就感觉要dp了
t*3
6 楼
三哥还是应该发挥他们的技术特点，直接强奸就搞定了
s*u
7 楼
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;
}
};
double slope;
double intercept;
Line(Point p, Point q){
if(p.x == q.x){
slope = numeric_limits
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
return p.x == (int)line.intercept;
return abs(p.x * line.slope + line.intercept - p.y) < 0.000000001;
}
class Solution {
public:
int maxPoints(vector
// 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
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
8 楼
不要用slope 跟hashmap 做。。。耗了好多时间
用三点共线
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
用三点共线
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
s*u
9 楼
我是找到那条线，然后再扫一遍，看在这条线上有多少个点。否则的话，比如单一个点
，就没法解决。因为有无限种可能。
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
，就没法解决。因为有无限种可能。
【在 D****6 的大作中提到】
: 这题怎么做？算slope和yintercept,再用个hashmap count.怎么count比较好？而且好
: 像同一个点不能只算一次，count起来比较复杂。有什么简单做法没？
w*s
10 楼
牛人，居然用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);
}
};
后看点是不是在那个上面？
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
11 楼
我写的，利用输入为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
int max=0, repeat=1;
Map map=new HashMap();
for (int j=i+1; 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();
public int maxPoints(Point[] points) {
assert(points!=null);
if (points.length<2) return points.length;
int globalMax=0;
for (int i=0; i
int max=0, repeat=1;
Map
for (int j=i+1; 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
s*u
12 楼
就是优先看斜率，再看截距。比较函数要注意严格弱序。只要定义了严格弱序，那么“
=”就相当于 非'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;
=”就相当于 非'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
13 楼
我们可以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起来比较复杂。有什么简单做法没？
点跟它的线的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
14 楼
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我觉得不错。
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
15 楼
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
:
: 且好
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
16 楼
不明白同一个点应该算两次？
Input: [(0,0),(0,0)]
Output: 1
Expected: 2
Input: [(0,0),(0,0)]
Output: 1
Expected: 2
s*p
17 楼
重复的点肯定共线，所以都要算进去。
【在 D***0 的大作中提到】
: 不明白同一个点应该算两次？
: Input: [(0,0),(0,0)]
: Output: 1
: Expected: 2
【在 D***0 的大作中提到】
: 不明白同一个点应该算两次？
: Input: [(0,0),(0,0)]
: Output: 1
: Expected: 2
D*0
18 楼
我理解重复的点就算是一个点了，虽然在输入里给的是两个点，但是在坐标系里就是一
个点
【在 s*****p 的大作中提到】
: 重复的点肯定共线，所以都要算进去。
个点
【在 s*****p 的大作中提到】
: 重复的点肯定共线，所以都要算进去。
l*3
19 楼
斜率这里可以用分数来表示，所有的斜率都化成最简分数，这样就不怕精度了
q*m
20 楼
我的这个为什么超时了呢？ 斜率我用一对整数(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
: int max=0, repeat=1;
: Map map=new HashMap();
: for (int j=i+1; j
）比其他的斜率都大。斜率(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
int cur = 0;
if(points.size() <= 2)
{
return points.size();
}
for(int i = 0; i < points.size() - 1; ++i)
{
vector
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
: int max=0, repeat=1;
: Map
: for (int j=i+1; j
相关阅读