2019CCPC秦皇岛A

昨天训练赛打了重现赛 ，我卡了好久A，队友又卡了F，直接血崩。

调了一整天A，昨天还以为被__gcd卡了，结果是被map卡常，真是太草了。今天把昨天TLE的代码map改成了hash+unordered_map就过了。

反思：读题仍是我们队最大的问题，应该尽可能每句话都看清。觉得可以写的题可以尝试，但是应该尽量跟榜。

题解：分成询问点是直角点和非直角点考虑。利用map<pair<ll,ll>>存储无精度问题的斜率信息。但是map太慢了，并且我的写法用不到map的自动排序功能，因此可以用hash映射坐标、unordered_map提高插入/查询速度。

AC代码：

inline long long gethash(ll x, ll y)
{
return x * 2333 + y * 23333 + 100000007;
}
unordered_map<long long, int> mp;
unordered_map<long long, int> mp2[100010];
int x[2010];
int y[2010];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d %d", &x[i], &y[i]);
for (int i = 1; i <= n; i++) //预处理所有斜率
{
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
int x1 = x[i] - x[j];
int y1 = y[i] - y[j];
if (!x1)
{
mp2[i][INF]++;
mp2[j][INF]++;
}
else if (!y1)
{
mp2[i][0]++;
mp2[j][0]++;
}
else
{
int g = __gcd(x1, y1);
x1 /= g;
y1 /= g;
mp2[i][gethash(x1, y1)]++;
mp2[j][gethash(x1, y1)]++;
}
}
}
for (int i = 1; i <= q; i++)
{
int xx, yy;
scanf("%d %d", &xx, &yy);
mp.clear();
long long ans = 0;
for (int j = 1; j <= n; j++) //查询点是直角点
{
if (x[j] == xx && y[j] == yy)
continue;
if (xx - x[j] == 0)
{
mp[INF]++;
if (mp.count(0))
ans += mp[0];
}
else if (yy - y[j] == 0)
{
mp[(0)]++;
if (mp.count(INF))
ans += mp[INF];
}
else
{
int x1 = xx - x[j];
int y1 = yy - y[j];
int g = __gcd(x1, y1);
x1 /= g;
y1 /= g;
mp[gethash(x1, y1)]++;
if (mp.count(gethash(-y1, x1)))
ans += mp[gethash(-y1, x1)];
if (mp.count(gethash(y1, -x1)))
ans += mp[gethash(y1, -x1)];
}
}
for (int j = 1; j <= n; j++) //查询点是非直角点
{
int x1 = xx - x[j];
int y1 = yy - y[j];
if (x[j] == xx && y[j] == yy)
continue;
if (!x1)
{
if (mp2[j].count(0))
ans += mp2[j][0] / 2;
}
else if (!y1)
{
if (mp2[j].count(INF))
ans += mp2[j][INF] / 2;
}
else
{
int g = __gcd(x1, y1);
x1 /= g;
y1 /= g;
if (mp2[j].count(gethash(-y1, x1)))
ans += mp2[j][gethash(-y1, x1)] / 2;
if (mp2[j].count(gethash(y1, -x1)))
ans += mp2[j][gethash(y1, -x1)] / 2;
}
}
printf("%lldn", ans);
}
return 0;
}

最后

以上就是糟糕早晨为你收集整理的2019CCPC秦皇岛A的全部内容，希望文章能够帮你解决2019CCPC秦皇岛A所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。