九度1548平面上の点(テクニック問題)
5211 ワード
タイトルの説明:
平面上のn個の点を与えて、任意に1本の直線をして、せいぜいいくつかの点がちょうど直線上に落ちることができることを求めます.
構想
1.Leetcode上原題.解法は,まず1つの点を決定し,その後,この点に対する他の点の傾きを計算することである.
2.この問題は多点重ね合わせに注意し、傾きが無限大の場合
コードが9度テストに合格しなかった
平面上のn個の点を与えて、任意に1本の直線をして、せいぜいいくつかの点がちょうど直線上に落ちることができることを求めます.
構想
1.Leetcode上原題.解法は,まず1つの点を決定し,その後,この点に対する他の点の傾きを計算することである.
2.この問題は多点重ね合わせに注意し、傾きが無限大の場合
コードが9度テストに合格しなかった
#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;
int xs[200], ys[200];
int main() {
freopen("testcase.txt", "r", stdin);
int pointnum, x, y;
while(scanf("%d", &pointnum) != EOF) {
int retVal = 0, inf = 0, dup = 1;
for(int i = 0; i < pointnum; i ++) {
scanf("%d%d", &x, &y);
xs[i] = x, ys[i] = y;
}
for(int i = 0; i < pointnum; i ++) {
map<double, int> record;
int basex = xs[i], basey = ys[i];
for(int j = 0; j < pointnum; j ++) {
if(i == j) continue;
int newx = xs[j], newy = ys[j];
if(newx == basex && newy == basey) {
dup ++;
}else if(newx == basex) {
inf++;
}else{
record[((double)(newy-basey))/(newx-basex)] ++;
}
}
int party = 0;
map<double, int>::iterator it_map;
for(it_map = record.begin(); it_map != record.end(); it_map ++) {
party = max(party, it_map->second);
}
party = max(party, inf);
party += dup;
retVal = max(party, retVal);
}
printf("%d
", retVal);
}
return 0;
}