社区讨论

E 求调或hack

学术版参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhji02zy
此快照首次捕获于
2025/11/04 02:53
4 个月前
此快照最后确认于
2025/11/04 02:53
4 个月前
查看原帖
思路是算总的梯形数减去平行四边形的多余贡献。
CPP
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,b,a) for(int i=(b);i>=(a);i--)
#define ll long long
#define Int __int128
#define int long long
using namespace std;
const int maxn = 1e6+5 , inf = 1e9;
int n , a[maxn] , b[maxn] , tot , ans;
struct node
{
	int x , y;
	bool operator <(const node &a ) const
	{
		return x * a.y < a.x * y;
	}
	bool operator >(const node &a ) const
	{
		return x * a.y > a.x * y;
	}
	bool operator == (const node &a ) const
	{
		return x * a.y == a.x * y;
	}
};
map <node , map<int , int>> st;
node k(int x1 , int x2 , int y1 , int y2)
{
	node res;
	res.x=x1-x2,res.y=y1-y2;
	if (res.y == 0)res.x=inf;
	if (res.x * res.y < 0) res.x=res.x,res.y=-res.y;
	return res;
}
int len (int x1 , int x2 , int y1 , int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
signed main ()
{
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)st[k(a[i] , a[j] , b[i] , b[j])][len(a[i] , a[j] , b[i] , b[j])]++;
	}
	for (auto p : st)
	{
		auto x = p.second;
		int res = 1 , cnt = 0;
		for (auto q : p.second)
		{
			res*=q.second;
			cnt+=q.second;
			ans-=q.second*(q.second-1)/2;
		}
		ans+=cnt*(cnt-1);
	}
	cout << ans/2 << "\n";
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...