N각형의 면적을 구하는 문제다.
벡터의 외적으로 해결할 수 있다.
삼각형으로 쪼개서 $(\vec{a}\times\vec{b}) / 2$를 누적합하면 된다.
여기서 넓이를 절대값 씌운후에 누적합해서 계속 틀렸었는데 이러면 안된다.
벡터의 외적은 방향과도 연관이 있는것이기 때문에
7
-3 0
-3 4
1 7
0 0
3 2
3 -3
0 -4
다음과 같은 데이터에서 오류가 난다.
#include <cstdio>
typedef long long ll;
ll abs(ll x) { return x < 0 ? -x : x; }
struct Vector {
ll x, y;
Vector() {}
Vector(ll xx, ll yy) :x(xx), y(yy) {}
Vector operator-(const Vector &other) {
return Vector(x - other.x, y - other.y);
}
ll cross(const Vector &other) {
return x*other.y - y*other.x;
}
};
ll ccw(Vector a, Vector b) {
return a.cross(b);
}
ll ccw(Vector p, Vector a, Vector b) {
return (a - p).cross(b - p);
}
int N;
Vector point[10001];
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%lld%lld", &point[n].x, &point[n].y);
ll ans = ccw(point[0], point[1], point[2]);
for (int n = 3;n < N;n++) {
ans += ccw(point[0], point[n - 1], point[n]);
}
printf("%.1lf\n", (double)abs(ans) / 2.0);
return 0;
}
| cs |
그리고 밑의 코드의 방식으로도 N각형의 면적을 구할 수 있다.
https://www.mathopenref.com/coordpolygonarea2.html 를 참고하자!
#include <cstdio>
typedef long long ll;
inline ll abs(ll x) { return x < 0 ? -x : x; }
struct point { ll x, y; };
int N;
point p[10000];
int main() {
scanf("%d", &N);
ll ans = 0;
for (int n = 0;n < N;n++) scanf("%lld%lld", &p[n].x, &p[n].y);
for (int n = 0;n < N;n++) {
if (n == 0) ans += (p[n].x + p[N - 1].x)*(p[n].y - p[N - 1].y);
else ans += (p[n].x + p[n - 1].x)*(p[n].y - p[n - 1].y);
}
printf("%.1lf\n", (double)abs(ans) / 2.0);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기