社区讨论
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 条回复,欢迎继续交流。
正在加载回复...