글 읽기 - convex hull 후 삼분탐색

wnguscjf01 2년 전 0

convex hull을 구한 뒤 사각형의 마주보는 두 점을 잡고 삼분탐색으로 넓이 최대되는 점 2개를 찾는 방식입니다. 반례 부탁드립니다.

#include<bits/stdc++.h>
#define MAXN 2001
using namespace std;
typedef long long int ll;
int stp, n;
pair<ll,ll> in[MAXN], O, st[MAXN];
ll cross(pair<ll,ll> v1, pair<ll,ll> v2){
	return v1.first*v2.second - v1.second*v2.first;
}
bool cmp(const pair<ll,ll> a, const pair<ll,ll> b){
	pair<ll,ll> v2={b.first-O.first,b.second-O.second};
	pair<ll,ll> v1={a.first-O.first,a.second-O.second};
	if(cross(v2,v1)==0 && a.first!=b.first) return a.first < b.first;
	if(cross(v2,v1)==0) return a.second < b.second;
	return cross(v2,v1) > 0;
}
ll get(int s, int b1, int b2){
	pair<ll,ll> v1, v2;
	v1 = {st[b1].first-st[s].first, st[b1].second-st[s].second};
	v2 = {st[b2].first-st[s].first, st[b2].second-st[s].second};
	return abs(cross(v1,v2));
}
ll tern(int s, int e, int b1, int b2){
	if(e-s==0) return get(s,b1,b2);
	if(e-s==1) return max(get(s,b1,b2), get(s+1,b1,b2));
	if(e-s == 2) return max(get(s,b1,b2),max(get(s+1,b1,b2),get(s+2,b1,b2)));
	if(get(s+(e-s+1)/3, b1, b2) > get(e-(e-s+1)/3, b1, b2)) return tern(s+(e-s+1)/3, e, b1, b2);
	return tern(s, e-(e-s+1)/3, b1, b2);
}
int main()
{
	int t, i, j, k;
	cin >> t;
	for(i=1; i<=t; i++){
		scanf("%d",&n);
		for(j=1; j<=n; j++){
			ll a, b;
			scanf("%lld%lld",&a,&b);
			in[j] = {a,b};
		}
		for(j=1; j<=n; j++){
			if(in[j].first < in[1].first || (in[j].first==in[1].first && in[j].second < in[1].second)){
				pair<ll,ll> tmp=in[1]; in[1]=in[j]; in[j]=tmp;
			}
		}
		O = in[1];
		sort(in+2, in+n+1, cmp);
		st[0] = in[1]; stp=0;
		for(j=2; j<=n; j++){
			st[++stp] = in[j];
			pair<ll,ll> tmp1, tmp2;
			while(stp>1){
				tmp1={st[stp-1].first-st[stp-2].first,st[stp-1].second-st[stp-2].second};
				tmp2={st[stp].first-st[stp-1].first,st[stp].second-st[stp-1].second};
				if(cross(tmp1,tmp2) <= 0) break;
				st[stp-1] = st[stp]; stp--;
			}
		}
		st[++stp] = in[1];
		pair<ll,ll> tmp1, tmp2;
		while(stp>1){
			tmp1={st[stp-1].first-st[stp-2].first,st[stp-1].second-st[stp-2].second};
			tmp2={st[stp].first-st[stp-1].first,st[stp].second-st[stp-1].second};
			if(cross(tmp1,tmp2) <= 0) break;
			st[stp-1] = st[stp]; stp--;
		}
		stp--;
		if(stp==2){
			ll maxi = abs(cross({st[2].first-st[0].first,st[2].second-st[0].second}, {st[1].first-st[0].first,st[1].second-st[0].second}));
			if(maxi%2) printf("%lld.5\n",maxi/2);
			else printf("%lld\n",maxi/2);
			continue;
		}
		for(j=0; j<=stp; j++) st[j+stp+1] = st[j];
		ll maxi=0;
		for(j=0; j<=stp; j++){
			for(k=2; k<=stp-1; k++){
				ll p1=tern(j+1,j+k-1,j,j+k), p2=tern(j+k+1,j+stp,j+k,j+stp+1);
				maxi = max(maxi, p1+p2);
			}
		}
		if(maxi%2) printf("%lld.5\n",maxi/2);
		else printf("%lld\n",maxi/2);
	}
	return 0;
}

wnguscjf01 2년 전 0

아 삼분탐색에서 어이없는 실수를 했네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

convex hull 후 삼분탐색

wnguscjf01 2년 전 0

wnguscjf01 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말