北京集训TEST13——PA（Goodness）

题目：

Description

桌面上放有 n 张卡牌。对于每张卡牌，一面是绿色的，另一面是红色的。卡牌的每一面都标有一个整数。对于卡牌a和卡牌b，卡牌a对卡牌b的好感度为卡牌a绿色面的数与卡牌b红色面的数的乘积。

举个例子，如果卡牌a绿色面标有10，红色面标有3；卡牌b绿色面标有7，红色面标有-2。那么a对b的好感度为 10×(−2)=−20 ，b对a的好感度为 7×3=21 。则a和b的好感度的差异为 |21−(−20)|=41 。

现在，你知道这 n 张卡牌每一面的数，请你找出两张卡牌，使得他们好感度的差异最大。

Input

第一行为一个整数 n ，表示卡牌的数量。

接下来n行，每行两个整数 gi,ri ，分别表示第i张卡牌绿色面和红色面的数。

Output

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

Sample Input

Sample Output

HINT

【样例解释】

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

9×8−7×(−6)=114

【数据规模与约定】

对于20%的数据，n≤3000

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

对于所有数据，2≤n≤105,−109≤gi,ri≤109

题解：

解法：凸包。

首先，把(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+;

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=;

long long jdz(long long x)

{

  return x>?x:-x;

}

bool comp(int u,int v)

{

  long long det=(p[u]-p[])*(p[v]-p[]);

  if(det!=)  return det>;

  else return norm(p[u]-p[])<norm(p[v]-p[]);

}

bool compx(point a,point b)

{

  point po;

  po.x=,po.y=;

  point a1=a-po;

  point b1=b-po;

  if(a1*b1!=)  return a1*b1>;

  else return norm(a)<norm(b);

}

void tubao()

{

  int id=;

  for(int i=;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!=)  swap(p[id],p[]);

  int per[N];

  for(int i=;i<=n;i++)

    per[i]=i;

  sort(per+,per+n+,comp);

  q[++m]=p[];

  for(int i=;i<=n;i++)

  {

    int j=per[i];

    while(m>=&&(p[j]-q[m-])*(q[m]-q[m-])>=)  m--;

    q[++m]=p[j];

  }

  sort(q+,q+m+,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<=)

  {

      for(int i=;i<=n;i++)

      scanf("%lld%lld",&green[i],&red[i]);

    for(int i=;i<=n;i++)

      for(int j=;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=;i<=n;i++)

      scanf("%lld%lld",&p[i].x,&p[i].y);

    point temp;

    temp.x=;

    temp.y=;

    p[++n]=temp;

    tubao();

    for(int i=,j=;i<=m;i++)

    {

      while(true)

      {

        int k=j==n?:j+;

        if(area(i,j)>=area(i,k)) break;

        else j=k;

      }

      ans=max(ans,area(i,j));

    }

    printf("%lld\n",ans);

  }

  return ;

}

巴特西