반 나누기 (백준 31405)

안녕하세요. 오늘은 반으로 나눌 거예요.

문제

https://www.acmicpc.net/problem/31405

아이디어

Size[i]를 A1, Ai, Ai+1로 만들 수 있는 삼각형의 넓이라고 합시다 (2<=i<=N-1)
그리고 Sum[i]=Sum[i-1]+Size[i]라고 합시다.
그러면 전체 넓이의 절반은 Sum[N]/2가 됩니다. 이 값 이하의 값중 가장 큰 Sum[i]의 값을 찾으면 정답은 Ai와 Ai+1을 적당히 내분한 값이 됩니다. 이를 계산해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
#define db double
#define pii pair <db,db>
using namespace std;

db area(pii A, pii B, pii C)
{
    return ((A.first * B.second + B.first * C.second + C.first * A.second) - (A.second * B.first + B.second * C.first + C.second * A.first)) / 2;
}

db Size[202020] = { 0 }, sum[202020] = { 0 };
pii dots[202020] = { {0,0} };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i;
    db x, y;

    cin >> N;
    for (i = 1; i <= N;i++)
    {
        cin >> x >> y;
        dots[i] = { x,y };
        if (i >= 3) Size[i - 1] = area(dots[1], dots[i - 1], dots[i]);
        if (i >= 3) sum[i - 1] = sum[i - 2] + Size[i - 1];
    }
    //cout << sum[N - 1] << "\n";
    ll idx = upper_bound(sum + 2, sum + N, sum[N - 1] / 2) - sum;
    //cout << idx;

    cout << "YES\n1 0\n" << idx << ' ';
    cout << fixed; cout.precision(10);
    cout << (sum[N - 1] / 2 - sum[idx - 1]) / Size[idx];
}

감사합니다.