[BOJ] 2166 : 다각형의 면적
풀이
외적
CCW라고도 하고 신발끈공식이라도 하는 외적 공식을 사용하면 다각형의 면적을 구할 수 있다.
세점을 알때 세점으로 두벡터를 만들어서 외적하면 크기가 평행사변형 넓이이고, 나누기2하면 삼각형의 넓이를 구할 수 있다.
x1y2 + x2+y3 + … + x(n)y1 - y1x2 - y2x3 - … - y(n)*x1 을 구한뒤 나누기 2하면된다.
반복해서 합칠때 마지막 항에만 주의하자.(처음값을 곱해주기 때문)
그리고 이문제같은 경우 int범위를 넘어가기 때문에 데이터 타입을 잘 정해줘야하는데,
저번에도 long long때문에 골치아팠는데 또 실수했다.
이부분 1LL를 곱해주는 것을 안해주니까 계속 틀렸다고 나온것이다.
sum += (1LL*v[i].first*v[i+1].second - 1LL*v[i+1].first*v[i].second);
앞으로는 long long 값에 int값을 곱해 넣을때 1LL을 꼭 꼭 붙이자!
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
using namespace std;
int main()
{
int n;
cin>>n;
vector<pair<int,int>> v;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
v.push_back({a,b});
}
double ans=0;
long long sum=0;
for(int i=0;i<n-1;i++){
sum += (1LL*v[i].first*v[i+1].second - 1LL*v[i+1].first*v[i].second);
}
sum += (1LL*v[n-1].first*v[0].second - 1LL*v[n-1].second*v[0].first);
if(sum<0)
sum=-sum;
ans=sum/2.0;
printf("%.1lf",ans);
return 0;
}
Written on April 30, 2019