| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
同为o(n ^ 2 log(n)), sort可过,map会tle
#include <stdio.h>
#include <map>
#include <algorithm>
//#define MAP
using namespace std;
const int MAX = 700;
int gcd(int a, int b)
{
if(a == 0 || b == 0) return 0;
else
{
if(a < 0) a = -a;
if(b < 0) b = -b;
if(a < b)
{
int c = a;
a = b;
b = c;
}
int c = a % b;
while(c > 0)
{
a = b;
b = c;
c = a % b;
}
return b;
}
}
int main()
{
int n;
while(scanf("%d", &n) && n)
{
int p[MAX][2];
for(int i = 0; i < n; i++) scanf("%d%d", &p[i][0], &p[i][1]);
int max = 0;
for(int i = 0; i < n; i++)
{
#ifdef MAP
map<pair<int, int>, int> m;
#else
pair<int, int> dis[MAX];
int pos = 0;
#endif
int same = 0;
for(int j = i + 1; j < n; j++)
{
int dx = p[i][0] - p[j][0];
int dy = p[i][1] - p[j][1];
if(dx == 0 && dy == 0) same++;
else
{
int c = gcd(dx, dy);
if(c == 0)
{
if(dx == 0 && dy != 0) dy = 1;
else if(dy == 0 && dx != 0) dx = 1;
}
else if(c != 1 && c != -1)
{
dx /= c;
dy /= c;
}
if(dx < 0)
{
dx = -dx;
dy = -dy;
}
#ifdef MAP
m[make_pair(dx, dy)]++;
#else
dis[pos++] = make_pair(dx, dy);
#endif
}
}
#ifdef MAP
for(map<pair<int, int>, int>::iterator it = m.begin(); it != m.end(); it++)
{
if((*it).second + same > max) max = (*it).second + same;
}
#else
sort(dis, dis + pos);
int v = same;
for(int i = 1; i < pos; i++)
{
if(dis[i] == dis[i - 1]) v++;
else
{
if(max < v) max = v;
v = same;
}
}
if(max < v) max = v;
#endif
}
#ifdef MAP
printf("%d\n", max + 1);
#else
printf("%d\n", max + 2);
#endif
}
}
时间浪费在算最大公约数上,不过比除法安全。但是map会tle实在让人惊讶
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator