输入 2 3
输出 3
by Limit @ 2019-05-02 07:56:29
~~去你的萌新~~
by wxwoo @ 2019-05-02 07:58:16
~~去你的萌新~~
by A_Big_Jiong @ 2019-05-02 08:01:06
真正的萌新自闭了
by wxy_god @ 2019-05-02 08:02:08
~~这是a+b吗~~
by lxyzphw @ 2019-05-02 08:03:01
~~去你的萌新~~
by zzy2333 @ 2019-05-02 08:05:48
我寻思着你不是A过A+B吗
by Meatherm @ 2019-05-02 08:07:35
~~去你的萌新~~
by Doveqise @ 2019-05-02 08:07:44
```cpp
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{double x,y;};
double sqr(double a)
{return a*a;}
int n,h,t,a,b,spj;
point Point[100001],check[100001];
bool cmp(point a,point b)
{
if(a.y!=b.y)return a.y>b.y;
return a.x>b.x;
}
double far(point a,point b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
double dis(point a,point b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
double side(point a,point b,point c)
{return a.x*b.y+a.y*c.x+b.x*c.y-a.x*c.y-a.y*b.x-b.y*c.x;}
double cha(point a,point b,point c)
{return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
void Around(int n)
{
h=n+1;
t=n+1;
int i;
check[t++]=Point[1];
for(i=1;i<=n;i++)
{
check[t]=Point[i];
if(side(check[n],Point[i],Point[i+1]))break;
}
if(n<2)return;
check[++t]=check[--h]=Point[++i];
if(side(check[n+1],check[n+2],check[n+3])<0)swap(check[n+1],check[n+2]);
for(++i;i<=n;i++)
{
if(side(check[h+1],check[h],Point[i])<0&&side(check[t-1],check[t],Point[i])>0)continue;
while(t-h>1&&side(check[h+1],check[h],Point[i])>=0)++h;
check[--h]=Point[i];
while(t-h>1&&side(check[t-1],check[t],Point[i])<=0)--t;
check[++t]=Point[i];
}
}
void solve(int num)
{
int max_y=-1e6,min_y=1e6,i,j;
int max_y_id,min_y_id;
for(i=1;i<=num;i++)
{
if(check[i].y>max_y)max_y=check[i].y,max_y_id=i;
if(check[i].y<min_y)min_y=check[i].y,min_y_id=i;
}
double ans=dis(check[max_y_id],check[max_y_id]);
check[num+1]=check[1];
for(j=1;j<=num;j++,min_y_id=min_y_id%num+1)
{
while(cha(check[min_y_id+1],check[max_y_id+1],check[min_y_id])>cha(check[min_y_id+1],check[max_y_id],check[min_y_id]))max_y_id=max_y_id%num+1;
ans=max(ans,dis(check[max_y_id],check[min_y_id]));
ans=max(ans,dis(check[max_y_id],check[min_y_id+1]));
}
cout<<(long long)(ans)*spj;
}
int main()
{
scanf("%d%d",&a,&b);
if(a==-b)
{
printf("0");
return 0;
}
n=4;
Point[1].x=a;
Point[1].y=0;
Point[2].x=-b;
Point[2].y=0;
Point[3].x=a;
Point[3].y=0.3;
Point[4].x=a;
Point[4].y=-0.3;
spj=1;
if(side(Point[3],Point[4],Point[2])>0)spj=-1;
sort(Point+1,Point+n+1,cmp);
Around(n);
int i;
for(i=h;i<t;i++)
check[i-h+1]=check[i];
solve(t-h);
return 0;
}
```
貌似真的不能两个点求直径...
自闭了
所以调成四个点就过了
$$\small\texttt{本}{}\huge\texttt{人}_{\small\texttt{的}^{\large\texttt{萌新}\small\texttt{QAQ}}}^{\large\texttt{是}_{\small\texttt{刚学}\large\texttt{OI}}}\huge\texttt{不得}^{\large\texttt{反}_{\small\texttt{驳}}}_{\small\texttt{...}}$$
by Limit @ 2019-05-02 08:09:22
@[A_Big_Jiong](/space/show?uid=84079) 在(0,a)和(0,-b)组成的凸包里求直径结果不就是a+b吗
by Limit @ 2019-05-02 08:10:28