- CCW (Counter Clockwise)
- 세점 p1(x1,y1), p2(x2,y2), p3(x3,y3) 이 있을 때 가능한 경우의 수 3가지
- 시계 방향 -1, 일직선 0, 반시계 방향 1
- 외적 공식 : 2S = (x2-x1)(y3-y1) - (y2-y1)(x3-x1)
- s > 0 : 반시계 방향
- s = 0 : 일직선
- s < 0 : 시계 방향
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
int temp = x1*y2+x2*y3+x3*y1;
temp = temp - y1*x2-y2*x3-y3*x1;
if (temp > 0) {
return 1;
} else if (temp < 0) {
return -1;
} else {
return 0;
}
}
출처
- list[] 에 있는 점들 중 가장 작은 것을 찾아서 기준점으로 선정한다. (보통 y기준)
- 기준점 기준으로 각각의 점들을 반시계 방향으로 기준점과 각도 순서대로 정렬한다.
- 점들을 하나씩 보면서 볼록껍질에 포함시킬지 말지를 결정한다.
- 스택을 하나 만들고, 이 스택에는 점의 번호를 넣어주는데 스택 사이즈가 한개밖에 없으면 일단 지금 잡고 있는 점을 넣는다.
- 스택에 점이 두 개 이상이면 비교를 한다.
- 점 두개를 기준으로 다른 점을 봤을 때 CCW를 하는데, 이 때 반시계 방향에 있으면 만족하므로 스택에 넣어준다.
- 그리고나서 또 스택의 두개를 빼서 두 점 기준으로 다음 점을 CCW 한다.
- 만약 반시계 방향에 없다면 오목하다는 의미이므로 만족하지 않는다. 따라서 이럴 경우에는 스택에서 빼준다.
- 이렇게 계속 반복해준다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;
class Hull{
int x, y;
Hull(int x, int y){
this.x = x;
this.y = y;
}
}
public class temp {
static int N;
static Hull list[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
list = new Hull[N+1];
for(int i=1; i<=N; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list[i] = new Hull(a, b);
}
// 1. 기준점 선정
for(int i=1; i<=N; i++){
if(list[1].y > list[i].y || list[1].y == list[i].y && list[1].x > list[i].x){
Hull temp = list[1];
list[1] = list[i];
list[i] = temp;
}
}
// 2. 기준점 기준으로 반시계방향으로 정렬
Arrays.sort(list, 2, N+1, new Comparator() {
@Override
public int compare(Hull a, Hull b) {
// TODO Auto-generated method stub
int v = ccw(new Hull(list[1].x, list[1].y), a, b);
if( v > 0) return -1;
if(v<0) return 1;
return (Math.abs(a.x) + a.y) - (Math.abs(b.x) + b.y);
}
});
// 3. stack
Stack stack = new Stack<>();
stack.push(1);
for(int i=2; i<=N; i++){
while(stack.size() > 1 && ccw(list[stack.get(stack.size()-2)], list[stack.peek()], list[i]) <=0 ){
stack.pop();
}
stack.add(i);
}
bw.write(stack.size() + "\n");
bw.flush();
}
protected static int ccw(Hull A, Hull B, Hull C) {
long cal = 0;
cal = (long)(B.x - A.x) * (C.y - A.y) - (long)(C.x-A.x) * (B.y-A.y);
if(cal > 0) return 1;
else if (cal< 0) return -1;
else return 0;
}
}
import java.io.*;
import java.util.*;
class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
ArrayList points = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
String belong = st.nextToken();
if (belong.equals("Y")) { // Y인 것만 볼록 껍질
points.add(new Point(x, y));
}
}
Stack result = grahamScan(points);
bw.write(result.size() + "\n");
for (int i = 0; i < result.size(); i++) {
bw.write(result.get(i).x + " " + result.get(i).y + "\n");
}
br.close();
bw.flush();
bw.close();
}
static Stack grahamScan(ArrayList input) throws IOException {
// 모든 점들을 x 오름차순으로 정렬하기
input.sort(new Comparator() {
@Override
public int compare(Point p1, Point p2) { // return 1이면 자리를 바꾼다
if (p1.x > p2.x) {
return 1;
} else if (p1.x == p2.x) {
if (p1.y > p2.y) {
return 1;
}
}
return -1;
}
});
Stack lower = new Stack<>(); // 아래 껍질
Stack upper = new Stack<>(); // 위 껍질
// 아래 껍질 계산
for (int i = 0; i < input.size(); i++) {
while (lower.size() > 1 && (ccw(lower.get(lower.size() - 2), lower.get(lower.size() - 1), input.get(i)) < 0)) { // first, second, next
lower.pop();
}
lower.add(input.get(i));
}
// 위 껍질 계산
for (int i = input.size() - 1; i >= 0; i--) {
while (upper.size() > 1 && (ccw(upper.get(upper.size() - 2), upper.get(upper.size() - 1), input.get(i)) < 0)) { // first, second, next
upper.pop();
}
upper.add(input.get(i));
}
lower.pop(); // 중복 제거
upper.pop();
lower.addAll(upper);
return lower;
}
static int ccw(Point p1, Point p2, Point p3) {
long result = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);
if (result > 0) { // 반시계 방향
return 1;
} else if (result < 0) { // 시계 방향
return -1;
} else {
return 0;
}
}
}
출처