紧急求助!!!直角坐标系的m个点,求同一条直线所能通过的最多点数
已知平面上(直角坐标系)的m个点,请编写一个函数,求同一条直线所能通过的最多点数。
谢谢各位啦!
[解决办法]
#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;}