读书人

!直角坐标系的m个点求同一条直线所

发布时间: 2012-02-23 22:01:35 作者: rapoo

紧急求助!!!直角坐标系的m个点,求同一条直线所能通过的最多点数
已知平面上(直角坐标系)的m个点,请编写一个函数,求同一条直线所能通过的最多点数。
谢谢各位啦!

[解决办法]

C/C++ code
#include <iostream>#include <deque>#include <vector>#include <map>using namespace std;struct POINT{    int dy, dx;    POINT(int _dy=0, int _dx = 0) : dy(_dy), dx(_dx){}};int operator < (const POINT& a, const POINT& b){    return a.dy < b.dy || a.dy==b.dy && a.dx<b.dx;}int  gcd(int a, int b){    return b ? gcd(b, a% b) : a;}int data[1005][2];int main(void){    int n;    while (scanf("%d", &n) == 1)    {                for (int i = 0; i < n; ++i)        {            scanf("%d%d",&data[i][0],&data[i][1]);        }        int m = -1;        for (int i = 0; i < n; ++i)        {            map<POINT, int> mp;            int s = 0;            int same = 0;            for (int j = i+1; j < n; ++j)            {                int dy = data[j][1] - data[i][1];                int dx = data[j][0] - data[i][0];                if (dx == 0 && dy == 0)                {                    ++same;continue;                }                int g = gcd(dx, dy);                if (g != 0)                {                    dy /= g;                    dx /= g;                }                if (dy < 0)                {                    dy = -dy;                    dx = -dx;                }                if (dx == 0) dy = 1;                if (dy == 0) dx = 1;                POINT t(dy,dx);                int k = ++mp[t];                s >?= k;            }            m >?= s+same+1;        }        printf("%d\n", m);            }    return 0;} 

读书人网 >软件架构设计

热点推荐