acm.hdu.edu.cn/showproblem.php?pid=6127
【题意】
- 给定平面直角坐标系中的n个点，这n个点每个点都有一个点权
- 这n个点两两可以连乘一条线段，定义每条线段的权值为线段两端点点权的乘积
- 现在要过原点作一条直线，要求这条直线不经过任意一个给定的点
- 在所有n个点两两连成的线段中，计算与这条直线有交点的线段的权值和
- 最大化这个权值和并输出
- 题目保证，给定的n个点不重合且任意两个点的连线不经过原点
【思路】
- 一条经过原点的直线把n个点分成两个半平面A,B
- 假设A中的点权分别为a1,a2....an;B中的点权分别为b1,b2,......bm。则结果为sumA*sumB
- 极角排序，枚举每个起点，线性扫一圈，计算半平面的点权之和，不断更新最优值
【AC】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm> using namespace std;
typedef long long ll;
const int maxn=5e4+;
int n;
double xx[maxn];
double yy[maxn];
ll val[maxn];
ll ans[maxn]; double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
const double eps = 1e-;
struct Point
{
double x;
double y;
ll val;
double dis;
double alf;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
Point(double _x,double _y,ll _val):x(_x),y(_y),val(_val){}
Point operator -(const Point &t) const
{
return Point(x-t.x,y-t.y);
}
double operator ^(const Point &t)const
{
return (x*t.y)-(y*t.x);
}
}p[maxn];
Point o(0.0,0.0);
bool cmp(const Point &a, const Point &b)//先按象限排序，再按极角排序，再按远近排序
{
if (a.y == && b.y == && a.x*b.x <= )return a.x>b.x;
if (a.y == && a.x >= && b.y != )return true;
if (b.y == && b.x >= && a.y != )return false;
if (b.y*a.y <= )return a.y>b.y;
return ((a-o)^(b-o))> 0.0 || (((a-o)^(b-o)) == 0.0 && a.x < b.x);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(ans,,sizeof(ans));
scanf("%d",&n);
ll sum=;
for(int i=;i<n;i++)
{
scanf("%lf%lf%I64d",&xx[i],&yy[i],&val[i]);
p[i]=Point(xx[i],yy[i],val[i]);
sum+=val[i];
}
sort(p,p+n,cmp);
int l=;
ll res;
ans[]+=p[].val;
for(int i=;i<n;i++)
{
if(i>) ans[i]=ans[i-]-p[i-].val;
while(((p[i]-o)^(p[l]-o))>)
{
ans[i]+=p[l].val;
l=(l+)%n;
}
if(i==) res=ans[i]*(sum-ans[i]);
else res=max(res,ans[i]*(sum-ans[i]));
}
printf("%I64d\n",res);
}
return ;
}
极角排序+线性扫模板
【模板】
bool cmp(const Point &a, const Point &b)//先按象限排序，再按极角排序，再按远近排序
{
if (a.y == && b.y == && a.x*b.x <= )return a.x>b.x;
if (a.y == && a.x >= && b.y != )return true;
if (b.y == && b.x >= && a.y != )return false;
if (b.y*a.y <= )return a.y>b.y;
return ((a-o)^(b-o))> 0.0 || (((a-o)^(b-o)) == 0.0 && a.x < b.x);
}
极角排序，o是中心点
int l=;
ll res;
// ans[0]+=p[0].val;
for(int i=;i<n;i++)
{
//if(i>0) ans[i]=ans[i-1]-p[i-1].val;
while(((p[i]-o)^(p[l]-o))>)
{
// 必要的运算
l=(l+)%n;
}
//这里更新答案
}
线性扫