北京集训TEST13——PA（Goodness）

题目：

Description

桌面上放有

举个例子，如果卡牌a绿色面标有10，红色面标有3；卡牌b绿色面标有7，红色面标有-2。那么a对b的好感度为

现在，你知道这

Input

第一行为一个整数

接下来n行，每行两个整数

Output

输出一个整数：好感度差异的最大值。

Sample Input

Sample Output

HINT

【样例解释】

第2张和第4张牌的好感度的差异最大：

9 \times 8 - 7 \times (- 6) = 114

【数据规模与约定】

对于20%的数据，

对于另外20%的数据，数据保证随机

对于所有数据，

题解：

解法：凸包。

首先，把(g[i], r[i])看成平面上的点，所求的值即为三角形（原点、a、b）面积的最大值的两倍（a, b为卡牌）。

其次，选出的两张卡牌一定是凸包上的点。下面证明：

假设两张卡牌都不是凸包上的点，则任选这两点中的一点a与原点O连成直线。则现在的目标是选择另外一点b使得三角形Oab的面积最大。将所有点往直线Oa作高发现，与直线Oa距离最远的点一定是凸包上的点，与假设矛盾。

假设一张卡牌a是凸包上的点，另一张卡牌b不是，仍可按照上面的方法证明b一定是凸包上的点，从而使假设矛盾。

如果数据是随机的话，把凸包上的点找出来（大概也就40个左右），O(n^2)枚举一下即可。

但是后面60%的数据都是我构造的，O(n^2)可能过不了（不排除有些同学水得比较高超把它们都水过了）～

我们可以枚举凸包上的一个点a，通过二分/三分找到离直线Oa最远的点。

本题标程时间复杂度O(n log n)

心得：

　　凸包的旋转卡壳的运用（注意枚举所有点··不然会漏，因为不一定是单峰的）

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=3e5+5;
struct point
{
  long long x;
  long long y;
}p[N],q[N];
inline point operator -(point a,point b)
{
  point t;
  t.x=a.x-b.x;
  t.y=a.y-b.y;
  return t;
}
inline long long operator *(point a,point b)
{
  return a.x*b.y-a.y*b.x;
}
inline long long norm(point a)
{
  return a.x*a.x+a.y*a.y;
}
int n,m;
long long green[N],red[N];
long long ans=0;
long long jdz(long long x)
{
  return x>0?x:-x;
}
bool comp(int u,int v)
{
  long long det=(p[u]-p[1])*(p[v]-p[1]);
  if(det!=0)  return det>0; 
  else return norm(p[u]-p[1])<norm(p[v]-p[1]);
}
bool compx(point a,point b)
{
  point po;
  po.x=0,po.y=0;
  point a1=a-po;
  point b1=b-po;
  if(a1*b1!=0)  return a1*b1>0;
  else return norm(a)<norm(b);
}
void tubao()
{
  int id=1;
  for(int i=2;i<=n;i++)
    if((p[i].x<p[id].x)||(p[i].x==p[id].x&&p[i].y<p[id].y))
      id=i;
  if(id!=1)  swap(p[id],p[1]);  
  int per[N];
  for(int i=1;i<=n;i++)
    per[i]=i;
  sort(per+2,per+n+1,comp);
  q[++m]=p[1];
  for(int i=2;i<=n;i++)
  {
    int j=per[i];
    while(m>=2&&(p[j]-q[m-1])*(q[m]-q[m-1])>=0)  m--;  
    q[++m]=p[j];
  }
  sort(q+1,q+m+1,compx);
}
long long area(int a,int b)
{
  return jdz(q[a]*q[b]);
}
int main()
{
 // freopen("a.in","r",stdin);
  //freopen("a.out","w",stdout);
  scanf("%d",&n);
  if(n<=3000)
  {
      for(int i=1;i<=n;i++)
      scanf("%lld%lld",&green[i],&red[i]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
        if(i==j)  continue;
        long long temp1=green[i]*red[j];
        long long temp2=green[j]*red[i];
        ans=max(ans,temp1-temp2);
      }
    printf("%lld",ans);
  }
  else
  {
    for(int i=1;i<=n;i++)
      scanf("%lld%lld",&p[i].x,&p[i].y);
    point temp;
    temp.x=0;
    temp.y=0;
    p[++n]=temp;
    tubao();
    for(int i=1,j=2;i<=m;i++)  
    {
      while(true)
      {
        int k=j==n?1:j+1;
        if(area(i,j)>=area(i,k)) break;
        else j=k;
      }
      ans=max(ans,area(i,j));
    }
    printf("%lld
",ans);
  }
  return 0;
}