[백준 12781] PIZZA ALVOLOC (C#, C++) - soo:bak

문제 링크

12781번 - PIZZA ALVOLOC

설명

원형 피자의 가장자리에서 네 개의 서로 다른 점을 선택하여 두 개의 선분을 만드는 상황에서, 8개의 정수 좌표가 주어질 때, 이 두 선분이 피자 내부에서 교차하여 피자를 네 조각으로 나누는지 판별하는 문제입니다.

두 선분이 내부에서 교차하면 1을, 그렇지 않으면 0을 출력합니다.

접근법

두 선분이 서로 교차하는지 판별하기 위해 CCW(Counter-Clock-Wise) 알고리즘을 사용합니다.

CCW는 세 점의 회전 방향을 판별하는 방법으로, 세 점 A, B, C가 주어질 때 벡터 AB에서 벡터 AC로의 회전 방향을 계산합니다.

세 점의 외적을 이용하면:

• 양수: 반시계 방향 (왼쪽으로 회전)
• 0: 일직선상에 위치
• 음수: 시계 방향 (오른쪽으로 회전)

두 선분 AB와 CD가 내부에서 교차하려면 다음 조건을 모두 만족해야 합니다:

1. 선분 AB를 기준으로 점 C와 점 D가 서로 반대편에 위치
2. 선분 CD를 기준으로 점 A와 점 B가 서로 반대편에 위치

이는 다음과 같이 확인할 수 있습니다:

• AB 기준으로 C의 방향과 D의 방향이 반대 (부호가 다름)
• CD 기준으로 A의 방향과 B의 방향이 반대 (부호가 다름)

예를 들어, 네 점이 (0,0), (2,2), (0,2), (2,0)이라면:

• 선분 1: (0,0) - (2,2)
• 선분 2: (0,2) - (2,0)

이 경우 두 선분은 (1,1)에서 교차하므로 1을 출력합니다.

반면 네 점이 (0,0), (1,0), (2,0), (3,0)처럼 일직선상에 있거나, 선분이 교차하지 않으면 0을 출력합니다.

문제 조건에서 네 점은 모두 서로 다르고 원의 가장자리에 있으므로, 세 점이 일직선상에 있는 경우는 고려하지 않아도 됩니다.

관련 문제: [백준 10255] 교차점 (C#, C++) - soo:bak

---

Code

C#

using System;

namespace Solution {
  class Program {
    struct Point {
      public long x, y;
      public Point(long x, long y) { this.x = x; this.y = y; }
    }

    static long Ccw(Point a, Point b, Point c) {
      var v = a.x * b.y + b.x * c.y + c.x * a.y;
      v -= a.y * b.x + b.y * c.x + c.y * a.x;
      if (v > 0) return 1;
      if (v < 0) return -1;
      return 0;
    }

    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      var p1 = new Point(long.Parse(input[0]), long.Parse(input[1]));
      var p2 = new Point(long.Parse(input[2]), long.Parse(input[3]));
      var p3 = new Point(long.Parse(input[4]), long.Parse(input[5]));
      var p4 = new Point(long.Parse(input[6]), long.Parse(input[7]));

      var abC = Ccw(p1, p2, p3);
      var abD = Ccw(p1, p2, p4);
      var cdA = Ccw(p3, p4, p1);
      var cdB = Ccw(p3, p4, p2);

      var cross = (abC * abD < 0) && (cdA * cdB < 0);
      Console.WriteLine(cross ? 1 : 0);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point { ll x, y; };

ll ccw(const Point& a, const Point& b, const Point& c) {
  ll v = a.x * b.y + b.x * c.y + c.x * a.y;
  v -= a.y * b.x + b.y * c.x + c.y * a.x;
  if (v > 0) return 1;
  if (v < 0) return -1;
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Point p1, p2, p3, p4;
  cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y;

  ll abC = ccw(p1, p2, p3);
  ll abD = ccw(p1, p2, p4);
  ll cdA = ccw(p3, p4, p1);
  ll cdB = ccw(p3, p4, p2);

  bool cross = (abC * abD < 0) && (cdA * cdB < 0);
  cout << (cross ? 1 : 0) << "\n";
  
  return 0;
}