WonYong-Jang
commented
5 years ago 볼록 껍질
public class Main {
static int N;
static Point[] p = new Point[100005];
static Point p0;
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int dx =0, dy =0;
p0 = new Point(40001,40001);
for(int i=1; i<= N; i++)
{
st = new StringTokenizer(br.readLine());
dx = Integer.parseInt(st.nextToken());
dy = Integer.parseInt(st.nextToken());
p[i] = new Point(dx, dy);
if(p0.dy > p[i].dy) {
p0.dx = p[i].dx;
p0.dy = p[i].dy;
}
if(p0.dy == p[i].dy && p0.dx > p[i].dx) {
p0.dx = p[i].dx;
p0.dy = p[i].dy;
}
}
Arrays.sort(p, 1, N+1, new mySort()); // 각 정렬 ( 반시계 방향 기준 )
stack.add(1);
stack.add(2);
int next = 3, second =0, first =0, op =0;
while(next <= N)
{
while(stack.size() >= 2)
{
second = stack.pop();
first = stack.peek();
op = ccw(p[first], p[second], p[next]);
if(op > 0) {
stack.add(second);
break;
}
}
stack.push(next++);
}
System.out.println(stack.size());
}
public static int ccw(Point a, Point b, Point c)
{
long tmp = ((long)(a.dx*b.dy) + (long)(b.dx*c.dy) + (long)(c.dx*a.dy)) - ((long)(a.dy*b.dx) + (long)(b.dy*c.dx) + (long)(c.dy*a.dx));
if(tmp > 0) return 1;
else if(tmp < 0) return -1;
else return 0;
}
public static long dis(Point a, Point b)
{
return (long)(a.dx-b.dx)*(a.dx-b.dx) + (long)(a.dy-b.dy)*(a.dy-b.dy);
}
static class mySort implements Comparator<Point> {
@Override
public int compare(Point a, Point b) {
int t = ccw(p0, a, b);
if(t == 0)
{
long d1 = dis(p0,a);
long d2 = dis(p0,b);
if(d1 < d2) return -1;
else if(d1 > d2) return 1;
else return 0;
}
return t > 0 ? -1 : 1;
}
}
static class Point {
int dx, dy;
Point(int a, int b) {
dx=a; dy=b;
}
}
}
ccw
다각형의 내부 외부 판별
다각형의 내부 외부 판별 구현
반직선과 선분 사이에 교점이 존재하기 위한 조건은 2가지
1) 점 B의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다. 2) 점 B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점 B의 좌표보다 크다.
public static boolean isCross(long tx, long ty) { int crossCnt = 0; long mindy =0, maxdy =0; for(int i=0; i< N; i++) { Point p1 = p[i]; Point p2 = p[(i+1) % N];
}