백준(BOJ) 16190 Rising Sun **

# ccw

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
pair<long long, long long> pos[2001];
pair<long long, long long> home;
int ans = -1;
long long ccw(pair<long long, long long> a, pair<long long, long long>b, pair<long long, long long> c)
{
	return a.first * b.second - b.first*a.second + b.first *c.second - c.first *b.second + c.first * a.second - a.first * c.second;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 2 * n; i++)
		scanf("%lld", &pos[i].first);
	scanf("%lld", &home.first);
	for (int i = 1; i < 2 * n; i++)
	{
		long long term = pos[i].first - pos[i - 1].first;
		if (i % 2 == 1)
			pos[i].second = pos[i - 1].second + term;
		else
			pos[i].second = pos[i - 1].second - term;
	}
	pos[2 * n].first = pos[2 * n - 1].first + pos[2 * n - 1].second;
	int i;
	for (i = 2 * n - 1; i >= 0; i--)
	{
		if (pos[i].first >= home.first)
			continue;
		if (i % 2 == 1)
			home.second = pos[i].second - (home.first - pos[i].first);
		else
			home.second = pos[i].second + (home.first - pos[i].first);
		break;
	}
	for (; i >= 0; i--)
	{
		if (ans == -1 || ccw(home, pos[ans], pos[i]) <= 0)
			ans = i;
	}
	if (ans == -1)
	{
		printf("0");
		return 0;
	}
	double aa = (double)(home.second - pos[ans].second) * (-home.first) / (home.first - pos[ans].first) + home.second;
	int aaa = ceil(aa);
	if (aaa < 0)
		aaa = 0;
	printf("%d", aaa);
	return 0;
}