백준15916 가희는 그래플러야!!

작성일 | In

문제 링크

  • http://icpc.me/15917

문제 출처

  • 제2회 천하제일 코딩대회 본선 A번

풀이

선분이 여러 개가 주어지고, y = kx 함수가 다른 선분들과 만나는 지점이 있는지 판단하는 문제입니다.
간단하게 CCW를 이용해 선분 교차 판별을 하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define x first
#define y second
#define st first
#define ed second
using namespace std;

typedef double db;
typedef pair<db, db> point;
typedef pair<point, point> line;

int ccw(point a, point b, point c){
	double value = a.x*b.y + b.x*c.y + c.x*a.y;
	value -= (a.y*b.x + b.y*c.x + c.y*a.x);
	if(value > 0.0) return 1;
	else if(value < 0.0) return -1;
	else return 0;
}

int crash(line _a, line _b){
	point a = _a.st, b = _a.ed, c = _b.st, d = _b.ed;
	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);
	if(!ab && !cd){
		if(a > b) swap(a, b);
		if(c > d) swap(c, d);
		return c<=b && a<=d;
	}
	return ab<=0.0 && cd<=0.0;
}

point arr[100010];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n; i++) arr[i].x = i, cin >> arr[i].y;
	double k; cin >> k;

	for(int i=1; i<=n; i++){
		point t1 = {i-1, k*(i-1)};
		point t2 = {i, k*i};
		line x = {arr[i-1], arr[i]};
		line y = {t1, t2};

		if(crash(x, y) && (arr[i-1].x || arr[i] == t2)){
			cout << "T";
			return 0;
		}
	}
	cout << "F";
}