글 읽기 - 10254번 고속도로 왜틀리나요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

kks227 8년 전 1

9240번 로버트 후드처럼 그냥 컨벡스홀 뽑고 회전하는 켈리퍼스 돌려서 푸는 문제가 아닌가요...?

44%까지 잘 가다가 갑자기 틀렸다고 합니다.

무슨 함정이 있나요?

일직선에만 있는 4개 이상의 점들에 대해서도 뽑아내는 듯 하고,

실수형 오차 날까봐 거리는 sqrt 안 씌우고 ull 타입으로 비교하고 있는데...

#include <cstdio>
#include <cmath>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> intPair;
typedef tuple<double, int, int> Point; // angle, x, y

double distance(const Point &A, const Point &B){
	return sqrt(pow(get<1>(A)-get<1>(B), 2.0) + pow(get<2>(A)-get<2>(B), 2.0));
}

double distance(const intPair &P){
	return sqrt(pow(P.first, 2.0) + pow(P.second, 2.0));
}

unsigned long long square(const Point &A, const Point &B){
	return 1ULL*(get<1>(A)-get<1>(B))*(get<1>(A)-get<1>(B)) + 1ULL*(get<2>(A)-get<2>(B))*(get<2>(A)-get<2>(B));
}

double ccw(const Point &A, const Point &B, const Point &C){
	return (get<1>(B)-get<1>(A))*(get<2>(C)-get<2>(A)) - (get<2>(B)-get<2>(A))*(get<1>(C)-get<1>(A));
}

double angle(const intPair &P, const intPair &Q){
	return acos((P.first*Q.first + P.second*Q.second)/distance(P)/distance(Q));
}

bool compare(const Point &A, const Point &B){
	if(get<0>(A) != get<0>(B)) return get<0>(A) > get<0>(B);
	if(get<2>(A) == get<2>(B)) return get<1>(A) < get<1>(B);
	return get<2>(A) > get<2>(B);
}

const intPair operator -(const intPair &P){
	return intPair(-P.first, -P.second);
}

const intPair operator -(const Point &P, const Point &Q){
	return intPair(get<1>(P)-get<1>(Q), get<2>(P)-get<2>(Q));
}

int main(){
	int T;
	scanf("%d", &T);
	for(int t=0; t<T; t++){
		int N;
		scanf("%d", &N);
		vector<Point> p(N);
		for(int i=0; i<N; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			p[i] = Point(0, x, y);
		}
		sort(p.begin(), p.end(), compare);
		for(int i=1; i<N; i++)
			get<0>(p[i]) = (get<1>(p[i])-get<1>(p[0]))/distance(p[0], p[i]);
		sort(p.begin()+1, p.end(), compare);

        // convex hull 만드는 부분
		vector<Point> hull;
		hull.push_back(p[0]);
		hull.push_back(p[1]);
		int P = 0, Q = 1, next = 2;
		int minY = get<2>(hull[1]);
		while(next < N){
			while(hull.size() >= 2){
				Point first, second;
				first = hull.back();
				second = hull[hull.size()-2];
				if(ccw(second, first, p[next]) < 0) break;
				hull.pop_back();
			}
			if(get<2>(p[next]) < minY ||
				get<2>(p[next]) == minY && get<1>(p[next]) > get<1>(p[Q]))
			{
				minY = get<2>(p[next]);
				Q = hull.size()-1;
			}
			hull.push_back(p[next++]);
		}
	
        // 가장 먼 두 점 구하는 부분
        // 시작시 P는 제일 위, Q는 제일 아래 점
		int hSize = hull.size();
		unsigned long long maxSquare = square(hull[P], hull[Q]);
		int resultP = P, resultQ = Q;
		intPair Pv(-1, 0);
		for(int i=0; i<hSize; i++){
			double Pa, Qa;
			Pa = angle(Pv, hull[(P+hSize-1)%hSize]-hull[P]);
			Qa = angle(-Pv, hull[(Q+hSize-1)%hSize]-hull[Q]);
			if(Pa <= Qa){
				Pv = hull[(P+hSize-1)%hSize]-hull[P];
				P = (P+hSize-1)%hSize;
			}
			else{
				Pv = hull[Q]-hull[(Q+hSize-1)%hSize];
				Q = (Q+hSize-1)%hSize;
			}
			if(maxSquare < square(hull[P], hull[Q])){
				maxSquare = square(hull[P], hull[Q]);
				resultP = P;
				resultQ = Q;
			}
		}
		printf("%d %d %d %d\n", get<1>(hull[resultP]), get<2>(hull[resultP]), get<1>(hull[resultQ]), get<2>(hull[resultQ]));
	} 
}

shjgkwo 8년 전 1

좀 노가다성이 짙어지겠지만 더블형 자체를 아예 안쓰고 풀어보심이..

shjgkwo 8년 전 4

저 같은 경우는 미세한 오차가 무서워 아예 기울기를 이용해서 로테이팅 캘리퍼스를 돌렸습니다.

더블아예 안쓰고 푼 경우입니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define rep(x) ((x)*(x))
#define _abs(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long ll;
struct bung {
    ll x;
    ll y;
    int d;
}o[200002];
bool fsort(bung a,bung b) {
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}
bool ccw(ll x1, ll y1, ll x2, ll y2, ll a, ll b) {
    ll d1 = x1*y2 + x2*b + a*y1;
    ll d2 = x2*y1 + a*y2 + x1*b;
    if(d1-d2 <= 0) return 1; // 시계
    return 0; // 반시계
}
bung stack[200002];
bool chk[200002];
int main() {
    int i, n;
    int k;
    int t;
    int top = 0;
    ll max1;
    int lq, lp;
    int e;
    ll a1, a2, b1, b2;
    ll tx1, ty1, tx2, ty2;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        memset(chk, 0, sizeof(chk));
        for(i=0;i<n;i++) scanf("%lld %lld",&o[i].x,&o[i].y);
        std::sort(o,o+n,fsort);
        for(i=0;i<n;i++) o[i].d = i;
        top = 0;
        stack[top++] = o[0];
        for(k=1;k<n-1;k++) if(o[0].y < o[k].y) break;
        stack[top++] = o[k];
        chk[o[k].d] = true;
        for(i=k+1;i<n;i++) {
            while(top > 1 && ccw(stack[top-2].x, stack[top-2].y, o[i].x, o[i].y, stack[top-1].x, stack[top-1].y)) top--, chk[stack[top].d] = false;
            stack[top++] = o[i];
            chk[o[i].d] = true;
        }
        e = top-1;
        for(i=n-2;i>=0;i--) {
            if(chk[i]) continue;
            while(top > 1 && ccw(stack[top-2].x, stack[top-2].y, o[i].x, o[i].y, stack[top-1].x, stack[top-1].y)) top--;
            stack[top++] = o[i];
        }
 
        lp = 0;
        lq = e;
        ll sav;
        max1 = 0;
        while (1) {
            sav = rep((stack[lp].x - stack[lq].x)) + rep(stack[lp].y - stack[lq].y);
            if (sav > max1) {
                max1 = sav;
                tx1 = stack[lp].x;
                ty1 = stack[lp].y;
                tx2 = stack[lq].x;
                ty2 = stack[lq].y;
            }
            if (lq == top - 1) lq = 0;
            if (lp == top - 1) break;
 
            a1 = (stack[lp].x - stack[lp + 1].x);
            b1 = (stack[lp].y - stack[lp + 1].y);
            a2 = (stack[lq].x - stack[lq + 1].x);
            b2 = (stack[lq].y - stack[lq + 1].y);
 
            if ((a1 == 0 && a2 == 0) || (b1 == 0 && b2 == 0)) {
                lp++;
                lq++;
            }
            else if (a1 == 0 && a2 != 0) lp++;
            else if (a1 != 0 && a2 == 0) lq++;
            else if (b1* (a1/_abs(a1)) * _abs(a2) > b2* (a2/_abs(a2)) * _abs(a1)) lp++;
            else if (b1* (a1/_abs(a1)) * _abs(a2) < b2* (a2/_abs(a2)) * _abs(a1)) lq++;
            else {
                lp++;
                lq++;
            }
        }
        printf("%lld %lld %lld %lld\n", tx1, ty1, tx2, ty2);
    }
    return 0;
}

kks227 8년 전 1

흐어어... 설마 정말로 double 오차 때문일런지... 한번 시도해 보겠습니다.

kks227 7년 전 1

@shjgkwo 풀었습니다!! 결국 실수 오차가 문제가 맞긴 했습니다.

실수 오차를 줄이기 위해 가능한 한 모든 꼼수를 다 시도해서 보완했더니 어떻게 어떻게 시행착오 끝에 맞았습니다.

도움 주셔서 감사합니다!

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

문제

문제

출처

ICPC

10254번 고속도로 왜틀리나요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

kks227 8년 전 1

shjgkwo 8년 전 1

shjgkwo 8년 전 4

kks227 8년 전 1

kks227 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말