#78204 (C++11) No.199 星を描こう

提出ソース

結果

問題	No.199 星を描こう
ユーザー	latte0119
提出日時	2016-02-26 21:11:19
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	8,317 bytes
コンパイル時間	1,564 ms
コンパイル使用メモリ	171,984 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-09 13:55:31
合計ジャッジ時間	2,142 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	1 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	1 ms 6,940 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;

const int COUNTER_CLOCKWISE = +1;
const int CLOCKWISE = -1;
const int ONLINE_BACK = +2;
const int ONLINE_FRONT = -2;
const int ON_SEGMENT = 0;

const double EPS=1e-6;
const double INF=1e10;
const double PI=acos(-1);

typedef complex<double> Point;
typedef complex<double> Vector;
typedef vector<Point> Polygon;

struct Line
{
	Point a, b;
	Line() {}
	Line(const Point &_a, const Point &_b)
	{
		a = _a; b = _b;
	}
};

//Lineのダミー
struct Segment
{
	Point a, b;
	Segment() {}
	Segment(const Point &_a, const Point &_b)
	{
		a = _a; b = _b;
	}
};

struct Circle
{
	Point c;
	double r;

	Circle() {}

	Circle(const Point &_c, const double &_r)
	{
		c = _c; r = _r;
	}
};

istream& operator >> (istream& is, Point &p)
{
	double x, y;
	is >> x >> y;
	p.real(x); p.imag(y);
	return is;
}

Segment ToSegment(const Line l)
{
	return Segment(l.a, l.b);
}

Line ToLine(const Segment s)
{
	return Line(s.a, s.b);
}

//誤差許容==
bool equals(const double &a, const double &b);
bool equals(const Vector &a, const Vector &b);

//Pointの比較
bool comp(const Point &a, const Point &b);

//角度変換マン
double toRad(double a);
double toDeg(double a);

//回転マン
Point rotate(Point p,double d);


//内積
double dot(const Vector &a, const Vector &b);

//内積
double cross(const Vector &a, const Vector &b);

//多角形の面積
double GetArea(const Polygon &g);

//反時計回り(O(1))
//条件:点が全て異なる
int CCW(const Point &p0, const Point &p1, const Point &p2);

//直行判定(O(1))
bool IsOrthogonal(const Vector &a, const Vector &b);
bool IsOrthogonal(const Line &l1, const Line &l2);

//平行判定(O(1))
bool IsParallel(const Vector &a, const Vector &b);
bool IsParallel(const Line &l1, const Line &l2);

//射影(O(1))
Point Project(const Line &s, const Point &p);

//反射(O(1))
Point Reflect(const Line &s, const Point &p);

//点と直線の距離
double GetDistance(const Line &l, const Point &p);

//点と線分の距離
double GetDistance(const Segment &s, const Point &p);

//線分と線分の距離
double GetDistance(const Segment &s1, const Segment &s2);

//直線と線分の交差判定(O(1))
bool Intersects(const Line &l, const Segment &s);

//線分交差判定
bool Intersects(const Segment &l1, const Segment &l2);

//直線と直線の交点(O(1))
Point GetIntersection(const Line &l1, const Line &l2);

//円と円の交点
//戻り値
//	サイズは交点の数
vector<Point> GetIntersection(const Circle &c1, const Circle &c2);

//多角形の点内包(O(n))
//戻り値
//  0:内包しない
//  1:内包する
//  2:線分上
int Contains(const Polygon &g, const Point &p);

//凸包(O(n))
//戻り値
//	x->yの順で最も小さい頂点から反時計回り
Polygon AndrewScan(Polygon &s);

//凸多角形の切断(O(n))
Polygon ConvexCut(const Polygon &g, const Line &l);


//-----------------------------------------------------------

bool equals(const double &a, const double &b)
{
	return abs(a - b) < EPS;
}

bool equals(const Vector &a, const Vector &b)
{
	return equals(a.real(), b.real()) && equals(a.imag(), b.imag());
}

bool comp(const Point &a, const Point &b)
{
	return equals(a.real(), b.real()) ? a.imag() < b.imag() : a.real() < b.real();
}

double dot(const Vector &a, const Vector &b)
{
	return a.real()*b.real() + a.imag()*b.imag();
}

double cross(const Vector &a, const Vector &b)
{
	return a.real()*b.imag() - a.imag()*b.real();
}

double GetArea(const Polygon &g)
{
    if(g.size()<3)return 0;
	double res = 0;
	for (int i = 1; i < g.size() - 1; i++)
	{
		res += cross(g[i] - g[0], g[i + 1] - g[0]);
	}
	return abs(res / 2);
}

int CCW(const Point &p0, const Point &p1, const Point &p2)
{
	Vector v1 = (Vector)(p1 - p0), v2 = p2 - p0;
	if (cross(v1, v2) > EPS) return COUNTER_CLOCKWISE;
	if (cross(v1, v2) < -EPS) return CLOCKWISE;
	if (dot(v1, v2) < -EPS) return ONLINE_BACK;
	if (abs(v1) < abs(v2)) return ONLINE_FRONT;
	return ON_SEGMENT;
}

bool IsOrthogonal(const Vector &a, const Vector &b)
{
	return equals(dot(a, b), 0.0);
}
bool IsOrthogonal(const Line &l1, const Line &l2)
{
	return equals(dot(l1.b - l1.a, l2.b - l2.a), 0.0);
}

bool IsParallel(const Vector &a, const Vector &b)
{
	return equals(cross(a, b), 0.0);
}
bool IsParallel(const Line &l1, const Line &l2)
{
	return equals(cross(l1.b - l1.a, l2.b - l2.a), 0.0);
}

Point Project(const Line &s, const Point &p)
{
	Vector v1 = s.b - s.a;
	Vector v2 = p - s.a;
	double r = dot(v1, v2) / norm(v1);
	return s.a + v1 * r;
}

Point Reflect(const Line &s, const Point &p)
{
	return p + (Project(s, p) - p) * 2.0;
}

double GetDistance(const Line &l, const Point &p)
{
	return abs(cross(l.a - l.b, p - l.a) / abs(l.b - l.a));
}

double GetDistance(const Segment &s, const Point &p)
{
	if (dot(s.b - s.a, p - s.a) < 0.0) return abs(p - s.a);
	if (dot(s.a - s.b, p - s.b) < 0.0) return abs(p - s.b);
	return GetDistance(ToLine(s), p);
}

double GetDistance(const Segment &s1, const Segment &s2)
{
	if (Intersects(s1, s2)) return 0.0;
	return min(min(GetDistance(s1, s2.a), GetDistance(s1, s2.b)),
			   min(GetDistance(s2, s1.a), GetDistance(s2, s1.b)));
}

bool Intersects(const Line &l, const Segment &s)
{
	return CCW(l.a, l.b, s.a)*CCW(l.a, l.b, s.b) != 1;
}

bool Intersects(const Segment &l1, const Segment &l2)
{
	return CCW(l1.a, l1.b, l2.a)*CCW(l1.a, l1.b, l2.b) <= 0 &&
		CCW(l2.a, l2.b, l1.a)*CCW(l2.a, l2.b, l1.b) <= 0;
}

Point GetIntersection(const Line &l1, const Line &l2)
{
	Vector a1 = l1.b - l1.a, a2 = l2.b - l2.a;
	Vector b1 = l2.a - l1.a, b2 = l1.a - l2.b;
	double s1 = cross(a1, b1) / 2, s2 = cross(a1, b2) / 2;
	return Point(l2.a.real() + a2.real()*s1 / (s1 + s2), l2.a.imag() + a2.imag()*s1 / (s1 + s2));
}

vector<Point> GetIntersection(const Circle &c1, const Circle &c2)
{
	vector<Point> res;
	double d, a, t;
	d = sqrt(norm((c2.c - c1.c)));
	if (d < abs(c1.r - c2.r) || c1.r + c2.r < d) return res; //交点が0
	a = acos((c1.r*c1.r + d*d - c2.r*c2.r) / (2 * c1.r*d));
	t = atan2(c2.c.imag() - c1.c.imag(), c2.c.real() - c1.c.real());
	res.push_back(Point(c1.c.real() + c1.r*cos(t + a), c1.c.imag() + c1.r*sin(t + a)));
	res.push_back(Point(c1.c.real() + c1.r*cos(t - a), c1.c.imag() + c1.r*sin(t - a)));
	if (equals(res[0], res[1])) res.pop_back(); //交点が1
	return res;
}

int Contains(const Polygon &g, const Point &p)
{
	Line l = Line(p, Point(INF, p.imag()));
	int cnt = 0, n = g.size();
	for (int i = 0; i < n; i++)
	{
		Vector a = g[i] - p;
		Vector b = g[(i + 1) % n] - p;
		if (CCW(g[i], g[(i + 1) % n], p) == 0) return 2; //線分上
		if (a.imag() > b.imag()) swap(a, b);
		if (a.imag() <= EPS && EPS < b.imag() && cross(a, b) > EPS) cnt++;
	}
	if ((cnt & 1) == 1) return 1; //内包する
	return 0; //内包しない
}


/*
Polygon AndrewScan(Polygon &s)
{
	if (s.size() <= 2) return s;
	sort(s.begin(), s.end(), comp);
	Polygon g;
	for (int i = 0; i < s.size(); i++)
	{
		//CCWのところを==COUNTER_CLOCKWISEにすると辺上を含む
		for (int n = g.size(); n >= 2 && CCW(g[n - 2], g[n - 1], s[i]) != CLOCKWISE; n--)
		{
			g.pop_back();
		}
		g.push_back(s[i]);
	}
	for (int i = s.size() - 2; i >= 0; i--)
	{
		for (int n = g.size(); CCW(g[n - 2], g[n - 1], s[i]) != CLOCKWISE; n--)
		{
			g.pop_back();
		}
		g.push_back(s[i]);
	}
	reverse(g.begin(), g.end());
	g.pop_back();
	return g;
}
*/

Polygon convex_hull(Polygon ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end(),comp);
  Polygon ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && CCW(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && CCW(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}

Polygon ConvexCut(const Polygon &g, const Line &l)
{
	Polygon res;
	for (int i = 0; i < g.size(); i++)
	{
		Segment s = Segment(g[i], g[(i + 1) % g.size()]);
		if (CCW(l.a, l.b, s.a) != -1) res.push_back(s.a);
		if (CCW(l.a, l.b, s.a)*CCW(l.a, l.b, s.b) == -1)
			res.push_back(GetIntersection(l, ToLine(s)));
	}
	return res;
}


#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back

signed main(){
    Polygon g(5);
    rep(i,5)cin>>g[i];
    g=convex_hull(g);
    if(g.size()==5)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード