本文主要是介绍soj2164Problem B:爱恨就在一瞬间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
据说soj外网访问不了,那就贴题目吧
本来应该很简单的题,却让我花了很多时间。。。不过学到了更多
开始我的思路就不正确,想的是先枚举两点,再找与这两点共线的点累加,这样以来复杂度就是10e9,根本跑不了,于是比赛时我就没做出来。。。。
吴大大教给我们的思路是,从1到n,枚举这个点与之后的所有点的斜率,再统计数量最多的哪个斜率。这样做的正确性在于,如果在某个枚举点可以取到最大值,且与他相连得点存在至少一个在他前面的话,这个最大值一定会在枚举前面哪个点时得到,故只需要枚举从一点开始往后的点。
对于具体的实现,我就各种学习了,吴大大的代码写的确实好,我终于明白了自己的编程能力和大牛之间差距有多大。。几乎每个地方我都会犯错而大大则写的几乎完美。。
对于怎么判断斜率相等,这里不是用的斜率,三维坐标也没有斜率这个说法,而是由于各点坐标都是整数,就可以将每个点的坐标除以各坐标值的最大公约数,但是相互平行的向量还有可能反向,这里又是让我开眼界的技巧了,如果可以想办法尽量让所有的向量都指向第一卦限。具体操作就是,如果x小于0,各点坐标就反向,因为如果x小于0的话必然要将向量反向;如果x==0且y<0;或x==0且y==0且z<0,也要反向,原因类似。。。虽然这个看起来也没什么,但让我自己想的话可能怎么都想不出来。。。这样,判断各向量共线时就直接比较是否相等就行了。
对于怎么统计共线的点,方法就是先对各向量排序,这样相同的向量(即原本平行而不一定相同的向量)就挨在一起了。而具体的代码实现我出了错误找了半天才找到,而大大写的我第一眼看上去感觉累赘,再看才觉得写的精妙而“不刊一码”,等下看具体代码
一段一段贴大大的代码吧:(注释全是我加的,希望能尽量理解大大的精髓)
const int maxN = 1000 + 10; // 常量声明用const 感觉应该会比我的define 要好一些,因为有了类型int gcd(int a, int b) { //gcd我自以为没什么问题,写的时候才发现一些微妙之处,一是gcd调用时不用对ab进行排序,二是负数的gcd在这里依然可以直接调用if( b == 0 ) return a; return gcd(b, a % b);
} struct point3 { int x, y, z; point3() {} point3(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {} inline point3 operator-(const point3 &s) const { return point3(x - s.x, y - s.y, z - s.z); } inline void unit() { //大大思维的厉害之处,学习了int d = gcd(x, gcd(y, z)); if( d ) x /= d, y /= d, z /= d; if( x < 0 ) x = -x, y = -y, z = -z; if( x == 0 && y < 0 ) x = -x, y = -y, z = -z; if( x == 0 && y == 0 && z < 0 ) x = -x, y = -y, z = -z; } inline bool operator<(const point3 &s) const { //每个函数都加了inline可见大大的谨慎,是我这种粗狂不能比的,不过话说回来,感觉上面那个函数加inline可能不太好,毕竟有递归啊。。而且我测试了下,好像差别也不大。。。可能题目里的数据量还是不够大,还是看不出差别。。if( x == s.x && y == s.y ) return z < s.z; if( x == s.x ) return y < s.y; return x < s.x; //这里也比我一般用的方式高明} inline bool operator==(const point3 &s) const { return x == s.x && y == s.y && z == s.z; } inline void in() { scanf("%d %d %d", &x, &y, &z); }
};<pre name="code" class="cpp">point3 p[maxN]; int n; point3 q[maxN]; int nq;
int gao(int idx) { //不太明白大大的主处理函数为什么要叫gao查了下词典也没找到是什么单词,可能是大大喜欢的人的名字吧^_^nq = 0; for(int i = idx + 1; i < n; i ++) //正如上面说的,只遍历之后的点 q[nq ++] = p[i] - p[idx]; for(int i = 0; i < nq; i ++) q[i].unit(); sort(q, q + nq); int res = 0; for(int i = 0; i < nq; ) { //看似平淡无奇,其实滴水不漏,我写的最初版本忽略了最后一个,就一直waint j = i; while( j < nq && q[i] == q[j] ) j ++; res = max(res, j - i); i = j; } return 1 + res;
} int main()
{ //freopen("data.in", "r", stdin); //freopen("data.out", "w", stdout); while( scanf("%d", &n) == 1 ) { for(int i = 0; i < n; i ++) p[i].in(); int res = 0; for(int i = 0; i < n; i ++) if( n - i < res ) //剪枝break; else res = max(res, gao(i)); printf("%d\n", res); } return 0;
}
</pre><br /><p></p><p><br /></p><p>向大大学习,向大大看齐</p><p>最后,还是贴上我的代码吧,虽然丑了点,至少留在这,将来看看自己是不是进步了,还是依然放纵自己</p><p></p><pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 1010
using namespace std;int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}int s[MAX][3];struct point3
{int x,y,z;point3(int _x,int _y,int _z):x(_x),y(_y),z(_z){}point3(){}inline void modify(){int a=gcd(x,gcd(y,z));//必须在前面,gcd 不分正负及大小if(a)x/=a,y/=a,z/=a;if(x<0)x=-x,y=-y,z=-z;else if(x==0&&y<0)x=-x,y=-y,z=-z;else if(x==0&&y==0&&z<0)x=-x,y=-y,z=-z;}bool operator<(point3 other)const{if(x==other.x&&y==other.y)return z<other.z;if(x==other.x)return y<other.y;return x<other.x;}bool operator==(point3 other){return x==other.x&&y==other.y&&z==other.z;}
}ss[MAX];int main()
{int n,i,j,t,p,maxx;while(scanf("%d",&n)==1){if(n<=2){for(i=0;i<n;i++)scanf("%d %d %d",&t,&t,&t);printf("%d\n",n);continue;}maxx=0;for(i=0;i<n;i++)scanf("%d %d %d",&s[i][0],&s[i][1],&s[i][2]);for(i=0;i<n;i++){t=0;//if(n-i+1<maxx)//这里没想清楚// break;for(j=i+1;j<n;j++){ss[t++]=point3(s[i][0]-s[j][0],s[i][1]-s[j][1],s[i][2]-s[j][2]);}for(j=0;j<t;j++)ss[j].modify();sort(ss,ss+t);for(j=0,p=1;p<=t;p++){//if(t-j<maxx)//不加就会tle// break;if(!(ss[j]==ss[p])){maxx=max(p-j-1,maxx);j=p;}}}printf("%d\n",maxx+2);}return 0;
}
这篇关于soj2164Problem B:爱恨就在一瞬间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!