ABC 016 D - 一刀両断
問題概要
多角形を1つの直線で分断すると、いくつに分断されるかを求める問題。
解法
公式解説がわかりやすい。
分割された多角形の数
= 切っている本数+1
= (多角形と線分の交点の数 / 2) +1
= (線分と交差する多角形の辺の本数 / 2) +1
ミス
写経。幾何は無理。
コード
/* 分割された多角形の数 = 切っている本数+1 = (多角形と線分の交点の数 / 2) +1 = (線分と交差する多角形の辺の本数 / 2) +1 */ #include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; typedef long long ll; typedef pair<int,int> pint; typedef vector<int> vint; typedef vector<pint> vpint; #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define EPS 1e-10//誤差で計算できるように #define equals(a, b) (fabs(a) - (b) < EPS) class Point{ public: double x, y; //コンストラクタ Point():x(0),y(0) {} Point(double x, double y):x(x),y(y) {} //Point(double x = 0, y = 0): x(x), y(y){} //ベクトルの演算を定義 Point operator + (Point p){ return Point(x + p.x, y + p.y); }//和 Point operator - (Point p){ return Point(x - p.x, y - p.y); }//差 Point operator * (double a){ return Point(a * x, a * y); }//スカラー倍 Point operator / (double a){ return Point(x / a, y / a); } //ベクトルの大きさ(原点からベクトルを表す点までの距離) double abs(){ return sqrt(norm()); } //ベクトルの大きさの2乗 double norm(){ return x * x + y * y; } //ベクトルの大小関係を表す演算を定義 bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; } bool operator == (const Point &p) const{ return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; //return equals(x, p.x) && equals(y, p.y); } }; typedef Point Vector;//場合に応じてPointとVectorを使い分けてわかりやすくできるように //ベクトルaとbの内積 double dot(Vector a, Vector b){ return a.x * b.x + a.y * b.y; } //ベクトルaとbの外積 double cross(Vector a, Vector b){ return a.x * b.y - a.y * b.x; } //反時計回りccw int ccw(Point p0, Point p1, Point p2){ Vector a = p1 - p0; Vector b = p2 - p0; //return値は変更すること if(cross(a, b) > EPS) return -2;//p0p1反時計回りの方向にp2 if(cross(a, b) < -EPS) return -1;//p0p1時計回りの方向にp2 if(dot(a, b) < -EPS) return 0;//p2p0p1の順で直線上にp2 if(a.norm() < b.norm()) return 1;//p0p1p2の順で直線上にp2 return 2;//p0p2p1の順で線分p0p1上にp2 } //線分p1p2と線分p3p4の交差判定 (ベクトルp1p2とベクトルp3p4) bool intersect(Point p1, Point p2, Point p3, Point p4){ //returnで-1と-2が帰ってこればいい return (ccw(p1, p2, p3) + ccw(p1, p2, p4) == -3 && ccw(p3, p4, p1) + ccw(p3, p4, p2) == -3); } int main(void){ double ax, ay, bx, by; cin >> ax >> ay >> bx >> by; Point p1, p2; p1.x = ax; p1.y = ay;//p0p1は図形を分断する直線 p2.x = bx; p2.y = by; int sum = 0;//線分と多角形の辺の交点の数 int n; cin >> n; int x[101], y[101]; rep(i, n){ scanf("%d %d", &x[i], &y[i]); } Point p3, p4; rep(i, n){ if(i != n - 1){ p3.x = x[i]; p3.y = y[i]; p4.x = x[i + 1]; p4.y = y[i + 1]; }else{ p3.x = x[i]; p3.y = y[i]; p4.x = x[0]; p4.y = y[0]; } if(intersect(p1, p2, p3, p4)) sum++;; } printf("%d\n", sum / 2 + 1); return 0; }