結果

問題 No.199 星を描こう
コンテスト
ユーザー kyuridenamida
提出日時 2015-04-29 00:13:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,101 bytes
コンパイル時間 2,527 ms
コンパイル使用メモリ 175,120 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:22:26
合計ジャッジ時間 2,859 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
#define rep(i,n) for(int (i) = 0 ; (i) < (int)(n) ; (i)++)
typedef complex<double> P;
typedef vector<P> G;
double EPS = 1e-9;
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
namespace std {bool operator < (const P& a, const P& b) {return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);} }
string itos(int n){
	stringstream ss; ss << n;
	return ss.str();
}

inline double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
inline double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

inline int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
inline bool intersectSP(const L &s, const P &p) {return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < 1e-9;}
P projection(const L &l, const P &p) {double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);return l[0] + t*(l[0]-l[1]);}

inline bool intersectSS(const L &s, const L &t) {
  //return Edge(s[0],s[1]).intersect(Edge(t[0],t[1]));
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
  
}

inline double distanceSP(const L &s, const P &p) {
	const P r = projection(s, p);
	if (intersectSP(s, r)) return abs(r - p);
	return min(abs(s[0] - p), abs(s[1] - p));
}
inline double area2(const G& P) {
	double A = 0;
	for (int i = 0; i < P.size(); ++i)A += cross(curr(P, i), next(P, i));
	return abs(A);
}

inline double distanceSS(const L &s, const L &t) {
	if (intersectSS(s, t)) return 0;
	return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}

P crosspoint(const L &l, const L &m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0];
	return m[0] + B / A * (m[1] - m[0]);
}

int main(){
	 vector<P> p(5);
	 for(int i = 0 ; i < 5 ; i++){
		double x,y;
		cin >> x >> y;
		p[i] = P(x,y);
	 }
	 sort(p.begin(),p.end());
	 do{
		int fail = false;
		for(int i = 0 ; i < p.size() ; i++){
			L l1 = L(curr(p,i),next(p,i));
			int ok = 0;
			for(int j = 0 ; j < p.size() ; j++){
				L l2 = L(curr(p,j),next(p,j));
				set<P> s;
				s.insert(l1[0]);
				s.insert(l1[1]);
				s.insert(l2[0]);
				s.insert(l2[1]);
				if( s.size() == 4 ){
					if( intersectSS(l1,l2) ){
						P cp = crosspoint(l1,l2);
						double mini = 1e9;
						mini = min(abs(cp-l1[0]),mini);
						mini = min(abs(cp-l1[1]),mini);
						mini = min(abs(cp-l2[0]),mini);
						mini = min(abs(cp-l2[1]),mini);
						if( mini > EPS ){
							ok++;
						}
					}
				}
			}
			if( ok != 2 ){
				fail = true;
			}
		}
		if(!fail) {
			cout << "YES" << endl;
			return 0;
		}
	 }while( next_permutation(p.begin(),p.end()) );
	 cout << "NO" << endl;
}
0