看了一下,是牛客周赛43E。
赛时没对叉积求绝对值(第62行),掉大分。
做法:
- 枚举两个点,将该点对投影到连线的中点上。
因为平行四边形的重心就是两条对角线的交点,我们枚举经过该重心的边即可。
为了避免浮点误差,中点坐标不除二。 - 对每一个中点,枚举两个向量并求出叉积,叉积的绝对值就是平行四边形的面积。
同理,给三个点求三角形面积也可以用叉积求,只是还要除个二。
注意叉积为 0 的情况,说明四点共线。
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
using namespace std;
using ld=long double;
using ll=long long;
using pll=pair<ll,ll>;
const ld INF=9e18;
const ld two=2;
const int N=1010;
ll x[N],y[N];
map<pll,vector<pll>> m;
bool check(ll dx1,ll dy1,ll dx2,ll dy2)
{
return dx1*dx2==-dy1*dy2;
}
ll cal(ll ax,ll ay,ll bx,ll by,ll cx,ll cy)
{
return (bx-ax)*(cy-ay)-(by-ay)*(cx-ax);
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll ans=-1;
ll dx1,dy1,dx2,dy2,f1,f2;
int n,k,i,j;
cin>>n;
for(i=1;i<=n;++i)
cin>>x[i]>>y[i];
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
m[{x[i]+x[j],y[i]+y[j]}].emplace_back(i,j);
for(auto &p:m)
{
auto &v=p.second;
k=v.size();
for(i=0;i<k;++i)
for(j=i+1;j<k;++j)
{
dx1=x[v[i].first]-x[v[i].second];
dy1=y[v[i].first]-y[v[i].second];
dx2=x[v[j].first]-x[v[j].second];
dy2=y[v[j].first]-y[v[j].second];
f1=cal(x[v[i].first],y[v[i].first],x[v[i].second],y[v[i].second],x[v[j].first],y[v[j].first]);
f2=cal(x[v[i].first],y[v[i].first],x[v[i].second],y[v[i].second],x[v[j].second],y[v[j].second]);
if(f1!=0&&f2!=0)
ans=max(ans,llabs(f1));
}
}
if(ans==-1)
cout<<-1;
else
cout<<ans<<".0";
return 0;
}

京公网安备 11010502036488号