글 읽기 - Cows 문제 데이터 이상한지 확인 좀 부탁드려요

highalps 8년 전 0

Convex hull로 넓이를 구한다음 50을 나누는 간단한 문제인데

자신감은 아니지만 전혀 틀릴거 같진 않은데 틀려서

혹시 데이터가 이상한 건지 확인 가능할까요? ㅠ

#include <stdio.h>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
 
struct dot {
    ll x, y;
    dot(ll x, int y) { this->x = x, this->y = y; }
    dot() {}
};
dot st;
 
ll ccw(dot a, dot b, dot c) {
    return (a.x*b.y + b.x*c.y + c.x*a.y) - (b.x*a.y + c.x*b.y + a.x*c.y);
}
 
bool cmp(dot a, dot b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmp2(dot a, dot b) {
    return ccw(st, a, b) < 0;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    vector <dot> ary(n);
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &ary[i].x, &ary[i].y);
    sort(ary.begin(), ary.end(), cmp);
    st = ary[0];
    sort(ary.begin() + 1, ary.end(), cmp2);
    vector <dot> vec;
    vec.push_back(ary[0]); vec.push_back(ary[1]);
 
    for (int i = 2; i < ary.size(); i++)
    {
        int e = vec.size() - 1;
        while (ccw(vec[e - 1], vec[e], ary[i]) > 0) {
            vec.pop_back();
            if (!(--e))break;
        }
        vec.push_back(ary[i]);
    }
    vec.push_back(vec[0]);
    ll f = 0, r = 0;
    for (int i = 0; i < vec.size() - 1; i++)
        f += vec[i].x*vec[i + 1].y;
    for (int i = 1; i < vec.size(); i++)
        r += vec[i].x*vec[i - 1].y;
    f = (f - r) / 2;
    if (f < 0)f = -f;
    printf("%lld\n", f / (ll)50);
 
}

ntopia 8년 전 1

n = 1 이나 n = 2 인 데이터

혹은 나무들이 전부 일직선상에 있는 데이터

등에 대해서 잘 나오시나요?

august14 8년 전 1

일직선위에 여러 점이 있는 경우가 문제가 되겠네요

highalps 8년 전 0

그렇군요 :)

제가 너무 과신했네요

감사합니다

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

문제

문제

출처

ICPC

Cows 문제 데이터 이상한지 확인 좀 부탁드려요

highalps 8년 전 0

ntopia 8년 전 1

august14 8년 전 1

highalps 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말