Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define endl '\n'
- long long gcd(long long a, long long b) {
- return a ? gcd(b%a, a) : b;
- }
- struct frac {
- double p, q;
- frac() {
- p = 0;
- q = 1;
- }
- frac(double pp) {
- p = pp;
- q = 1;
- }
- frac(double pp, double qq) {
- p = pp;
- q = qq;
- norm();
- }
- void norm() {
- if (fabs(p) < 1e18 && fabs(q) < 1e18) {
- long long g = gcd((long long)p,(long long)q);
- p /= g;
- q /= g;
- if (q < 0) {
- q *= -1;
- p *= -1;
- }
- }
- }
- frac operator+(const frac & o) const {
- double pp = p*o.q + q*o.p;
- double qq = q*o.q;
- return frac(pp, qq);
- }
- frac operator-(const frac & o) const {
- double pp = p*o.q - q*o.p;
- double qq = q*o.q;
- return frac(pp, qq);
- }
- frac operator*(const frac & o) const {
- double pp = p*o.p;
- double qq = q*o.q;
- return frac(pp, qq);
- }
- frac operator/(const frac & o) const {
- double pp = p*o.q;
- double qq = q*o.p;
- return frac(pp, qq);
- }
- bool operator < (const frac & o) const {
- return p*o.q < q*o.p;
- }
- };
- pair<frac, frac> center(const frac & x11, const frac & y11, const frac & x12, const frac & y12,
- const frac & x21, const frac & y21, const frac & x22, const frac & y22) {
- frac a1 = y12-y11;
- frac b1 = x11-x12;
- frac c1 = x11*(y12-y11) + y11*(x11-x12);
- frac a2 = y22-y21;
- frac b2 = x21-x22;
- frac c2 = x21*(y22-y21) + y21*(x21-x22);
- frac d = a1*b2 - b1*a2;
- frac d1 = c1*b2 - b1*c2;
- frac d2 = a1*c2 - a2*c1;
- return make_pair(d1/d, d2/d);
- }
- long long X[3][9333], Y[3][9333];
- map<pair<int,int>, int> mp;
- int mlen;
- int getidx(int x, int y) {
- if (mp.find(make_pair(x,y)) == mp.end()) {
- mp[make_pair(x,y)] = mlen++;
- }
- return mp[make_pair(x,y)];
- }
- vector<int> G[1111];
- int main( void ) {
- cin.tie( 0 ); cin.sync_with_stdio( 0 );
- int n;
- cin >> n;
- vector<pair<int,int> > VV;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < 3; j++) {
- cin >> X[j][i] >> Y[j][i];
- VV.push_back(make_pair(X[j][i], Y[j][i]));
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < 3; j++) {
- int x = X[j][i], y = Y[j][i];
- G[getidx(x,y)].push_back(i);
- }
- }
- sort(VV.begin(), VV.end());
- VV.resize(distance(VV.begin(), unique(VV.begin(), VV.end())));
- for (int i = 0; i < n; i++) {
- frac x11, y11, x12, y12;
- frac x21, y21, x22, y22;
- long long x1,y1,x2,y2;
- x1 = X[0][i], y1 = Y[0][i];
- x2 = X[1][i], y2 = Y[1][i];
- if (x1==x2) {
- y11 = frac(y1+y2,2);
- y12 = frac(y1+y2,2);
- x11 = frac(x1-1,1);
- x12 = frac(x1+1,1);
- } else if (y1==y2) {
- x11 = frac(x1+x2, 2);
- x12 = frac(x1+x2, 2);
- y11 = frac(y1-1);
- y12 = frac(y1+1);
- } else {
- x11 = frac(x1+x2, 2), y11 = frac(y1+y2, 2);
- x12 = x11 + frac(1), y12 = y11 + frac(x2-x1,2)/frac(y1-y2,2);
- }
- x1 = X[0][i], y1 = Y[0][i];
- x2 = X[2][i], y2 = Y[2][i];
- if (x1==x2) {
- y21 = frac(y1+y2, 2);
- y22 = frac(y1+y2, 2);
- x21 = frac(x1-1);
- x22 = frac(x1+1);
- } else if (y1==y2) {
- x21 = frac(x1+x2,2);
- x22 = frac(x1+x2,2);
- y21 = frac(y1-1);
- y22 = frac(y1+1);
- } else {
- x21 = frac(x1+x2, 2), y21 = frac(y1+y2, 2);
- x22 = x21 + frac(1), y22 = y21 + frac(x2-x1,2)/frac(y1-y2,2);
- }
- pair<frac,frac> p = center(x11, y11, x12, y12, x21, y21, x22, y22);
- frac cx = p.first, cy = p.second;
- frac dx = (frac(X[0][i])-cx), dy = (frac(Y[0][i])-cy);
- frac r = dx*dx + dy*dy;
- for (int kk = 0; kk < 3; kk++) {
- int xx = X[kk][i], yy = Y[kk][i];
- int idx = getidx(xx,yy);
- for (int jj = 0; jj < (int)G[idx].size(); jj++) {
- int j = G[idx][jj];
- for (int k = 0; k < 3; k++) {
- frac x = frac(X[k][j]), y = frac(Y[k][j]);
- if ((x.p == X[0][i] && y.p == Y[0][i]) ||
- (x.p == X[1][i] && y.p == Y[1][i]) ||
- (x.p == X[2][i] && y.p == Y[2][i])) continue;
- if ((x-cx)*(x-cx) + (y-cy)*(y-cy) < r) {
- cout << "NO" << endl;
- return 0;
- }
- }
- }
- }
- }
- cout << "YES" << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement