#유형 : CCW, 다각형의 넓이

#난이도 : 골드 V

#다각형의 넓이는 벡터의 외적으로 구할 수 있다 => 삼각형으로 쪼개서 외적을 누적하여 합하면 된다.

==다각형을 이루는 점 하나를 중심으로 잡고, 그 점을 중심으로 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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2166 {
    static int N;
    static Po[] p;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        p = new Po[N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            p[i] = new Po(x,y);
        }
        long res = 0;
        for(int i=2; i<N; i++) {
            res += ccw(p[1], p[i], p[i+1]);
        }
        
        res = Math.abs(res);
        if(res % 2 == 0) {
            System.out.println(res/2+".0");
        }else
            System.out.println(res/2+".5");
    }
    
    public static long ccw(Po p1, Po p2, Po p3) {
        //CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
        return ((p1.x*p2.y) + (p2.x*p3.y) + (p3.x * p1.y)) - ((p1.y*p2.x) + (p2.y*p3.x) + (p3.y*p1.x));
        
    }
    
    public static class Po{
        long x;
        long y;
        public Po(long x, long y) {
            this.x=x;
            this.y=y;
        }
    }
}
 
cs

'백준' 카테고리의 다른 글

#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30
#백준_1865 웜홀 - Java 자바  (0) 2020.04.28

+ Recent posts