【洛谷 P1452】 Beauty Contest （二维凸包，旋转卡壳）

题目链接

旋转卡壳模板题把。

有时间再补总结吧。

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAXN = 100010;

struct point{

	int x, y;

}p[MAXN];

int operator * (point a, point b){    // a x b

	return a.x * b.y - b.x * a.y;

}

point operator - (point a, point b){

	return (point){ a.x - b.x, a.y - b.y };

}

int cmp1(const point a, const point b){

	return a.x == b.x ? a.y < b.y : a.x < b.x;

}

inline double k(point a, point b){

	return a.x == b.x ? 1e18 : ((double)b.y - a.y) / (b.x - a.x);

}

inline double dis(point a, point b){

	int px = b.x - a.x, py = b.y - a.y;

	return sqrt(px * px + py * py);

}

inline int dp(point a, point b){

	int px = b.x - a.x, py = b.y - a.y;

	return px * px + py * py;

}

int n, top, tp, ans;

point st[MAXN], ts[MAXN];

inline double mult(point a, point b, point c){

	return (a - c) * (b - c);

}

int SpecialJudge(){

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

	   if(p[i].y != p[i - 1].y)

	     return 0;

	return 1;

}

int main(){

	scanf("%d", &n);

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

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

	if(SpecialJudge()){

	  int Min = 0x3f3f3f3f, Max = -0x3f3f3f3f;

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

	  	 Min = min(Min, p[i].x);

	  	 Max = max(Max, p[i].x);

	  }

	  printf("%d\n", (Max - Min) * (Max - Min));

	  return 0;

    }

	sort(p + 1, p + n + 1, cmp1);

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

	   while(top > 1 && k(st[top - 1], p[i]) < k(st[top - 1], st[top])) --top;

	   st[++top] = p[i];

    }

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

	   while(tp > 1 && k(ts[tp - 1], p[i]) > k(ts[tp - 1], ts[tp])) --tp;

	   ts[++tp] = p[i];

    }

    for(int i = tp - 1; i; --i) st[++top] = ts[i];

    int j = 2;

    for(int i = 1; i <= top; ++i){

       while(mult(st[i], st[i + 1], st[j]) < mult(st[i], st[i + 1], st[j + 1]))

       	 if(++j > top) j = 1;

       ans = max(ans, max(dp(st[i], st[j]), dp(st[i + 1], st[j])));

    }

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

	return 0;

}

巴特西

【洛谷 P1452】 Beauty Contest （二维凸包，旋转卡壳）

最新文章

热门文章