1 solutions
-
0
C++ :
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <queue> using namespace std; #define out(v) cerr << #v << ": " << (v) << endl #define SZ(v) ((int)(v).size()) const int maxint = -1u>>1; template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;} template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;} const double pi = acos(-1.0); const double eps = 1e-9; int sgn(double x) { return (x > eps) - (x < -eps); } int n; struct point { double x, y; point() {} point(double _x, double _y) : x(_x), y(_y) {} }; double dis(double x, double y) { return sqrt(x * x + y * y); } vector<point> pts; vector< pair<double, double> > vec; bool check(const vector< pair<double, double> > &vec) { for(int i = 0; i < vec.size(); i++) { double len = vec[i].first; double arc = vec[i].second; for(int j = i + 1; j < vec.size(); j++) { if(sgn(vec[j].first - len)) { i = j - 1; break; } else { if(sgn(arc - vec[j].second) == 0 || sgn(fabs(arc - vec[j].second) - pi) == 0) { } else { return true; } } } } return false; } bool getAnswer() { for(int i = 0; i < n; i++) { vec.clear(); for(int j = 0; j < n; j++) { if(i == j) continue; double arc = atan2(pts[j].y - pts[i].y, pts[j].x - pts[i].x); double len = dis(pts[j].y - pts[i].y, pts[j].x - pts[i].x); if(sgn(arc) < 0) arc += 2 * pi; vec.push_back(make_pair(len, arc)); } sort(vec.begin(), vec.end()); if(check(vec)) return true; } return false; } int main() { //freopen("tri.in") //freopen("tri.out", "w", stdout); while(scanf("%d", &n) == 1) { pts.clear(); for(int i = 0; i < n; i++) { double x, y; scanf("%lf%lf", &x, &y); pts.push_back(point(x, y)); } printf(getAnswer() ? "YES\n": "NO\n"); } return 0; }
- 1
Information
- ID
- 17301
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By