Advertisement
Guest User

Untitled

a guest
Nov 1st, 2015
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define endl                            '\n'
  6.  
  7. long long gcd(long long a, long long b) {
  8.         return a ? gcd(b%a, a) : b;
  9. }
  10.  
  11. struct frac {
  12.         double p, q;
  13.         frac() {
  14.                 p = 0;
  15.                 q = 1;
  16.         }
  17.         frac(double pp) {
  18.                 p = pp;
  19.                 q = 1;
  20.         }
  21.         frac(double pp, double qq) {
  22.                 p = pp;
  23.                 q = qq;
  24.                 norm();
  25.         }
  26.         void norm() {
  27.                 if (fabs(p) < 1e18 && fabs(q) < 1e18) {
  28.                         long long g = gcd((long long)p,(long long)q);
  29.                         p /= g;
  30.                         q /= g;
  31.                         if (q < 0) {
  32.                                 q *= -1;
  33.                                 p *= -1;
  34.                         }
  35.                 }
  36.         }
  37.         frac operator+(const frac & o) const {
  38.                 double pp = p*o.q + q*o.p;
  39.                 double qq = q*o.q;
  40.                 return frac(pp, qq);
  41.         }
  42.  
  43.         frac operator-(const frac & o) const {
  44.                 double pp = p*o.q - q*o.p;
  45.                 double qq = q*o.q;
  46.                 return frac(pp, qq);
  47.         }
  48.  
  49.         frac operator*(const frac & o) const {
  50.                 double pp = p*o.p;
  51.                 double qq = q*o.q;
  52.                 return frac(pp, qq);
  53.         }
  54.  
  55.         frac operator/(const frac & o) const {
  56.                 double pp = p*o.q;
  57.                 double qq = q*o.p;
  58.                 return frac(pp, qq);
  59.         }
  60.  
  61.         bool operator < (const frac & o) const {
  62.                 return p*o.q < q*o.p;
  63.         }
  64. };
  65.  
  66. pair<frac, frac> center(const frac & x11, const frac & y11, const frac & x12, const frac & y12,
  67.                                                 const frac & x21, const frac & y21, const frac & x22, const frac & y22) {
  68.         frac a1 = y12-y11;
  69.         frac b1 = x11-x12;
  70.         frac c1 = x11*(y12-y11) + y11*(x11-x12);
  71.  
  72.         frac a2 = y22-y21;
  73.         frac b2 = x21-x22;
  74.         frac c2 = x21*(y22-y21) + y21*(x21-x22);
  75.  
  76.         frac d = a1*b2 - b1*a2;
  77.         frac d1 = c1*b2 - b1*c2;
  78.         frac d2 = a1*c2 - a2*c1;
  79.         return make_pair(d1/d, d2/d);
  80. }
  81.  
  82. long long X[3][9333], Y[3][9333];
  83.  
  84. map<pair<int,int>, int> mp;
  85. int mlen;
  86. int getidx(int x, int y) {
  87.         if (mp.find(make_pair(x,y)) == mp.end()) {
  88.                 mp[make_pair(x,y)] = mlen++;
  89.         }
  90.         return mp[make_pair(x,y)];
  91. }
  92. vector<int> G[1111];
  93.  
  94. int main( void ) {
  95.         cin.tie( 0 ); cin.sync_with_stdio( 0 );
  96.         int n;
  97.         cin >> n;
  98.         vector<pair<int,int> > VV;
  99.         for (int i = 0; i < n; i++) {
  100.                 for (int j = 0; j < 3; j++) {
  101.                         cin >> X[j][i] >> Y[j][i];
  102.                         VV.push_back(make_pair(X[j][i], Y[j][i]));
  103.                 }
  104.         }
  105.         for (int i = 0; i < n; i++) {
  106.                 for (int j = 0; j < 3; j++) {
  107.                         int x = X[j][i], y = Y[j][i];
  108.                         G[getidx(x,y)].push_back(i);
  109.                 }
  110.         }
  111.         sort(VV.begin(), VV.end());
  112.         VV.resize(distance(VV.begin(), unique(VV.begin(), VV.end())));
  113.         for (int i = 0; i < n; i++) {
  114.                 frac x11, y11, x12, y12;
  115.                 frac x21, y21, x22, y22;
  116.                 long long x1,y1,x2,y2;
  117.                 x1 = X[0][i], y1 = Y[0][i];
  118.                 x2 = X[1][i], y2 = Y[1][i];
  119.                 if (x1==x2) {
  120.                         y11 = frac(y1+y2,2);
  121.                         y12 = frac(y1+y2,2);
  122.                         x11 = frac(x1-1,1);
  123.                         x12 = frac(x1+1,1);
  124.                 } else if (y1==y2) {
  125.                         x11 = frac(x1+x2, 2);
  126.                         x12 = frac(x1+x2, 2);
  127.                         y11 = frac(y1-1);
  128.                         y12 = frac(y1+1);
  129.                 } else {
  130.                         x11 = frac(x1+x2, 2), y11 = frac(y1+y2, 2);
  131.                         x12 = x11 + frac(1), y12 = y11 + frac(x2-x1,2)/frac(y1-y2,2);
  132.                 }
  133.  
  134.                 x1 = X[0][i], y1 = Y[0][i];
  135.                 x2 = X[2][i], y2 = Y[2][i];
  136.                 if (x1==x2) {
  137.                         y21 = frac(y1+y2, 2);
  138.                         y22 = frac(y1+y2, 2);
  139.                         x21 = frac(x1-1);
  140.                         x22 = frac(x1+1);
  141.                 } else if (y1==y2) {
  142.                         x21 = frac(x1+x2,2);
  143.                         x22 = frac(x1+x2,2);
  144.                         y21 = frac(y1-1);
  145.                         y22 = frac(y1+1);
  146.                 } else {
  147.                         x21 = frac(x1+x2, 2), y21 = frac(y1+y2, 2);
  148.                         x22 = x21 + frac(1), y22 = y21 + frac(x2-x1,2)/frac(y1-y2,2);
  149.                 }
  150.        
  151.                 pair<frac,frac> p = center(x11, y11, x12, y12, x21, y21, x22, y22);
  152.                 frac cx = p.first, cy = p.second;
  153.                 frac dx = (frac(X[0][i])-cx), dy = (frac(Y[0][i])-cy);
  154.                 frac r = dx*dx + dy*dy;
  155.                 for (int kk = 0; kk < 3; kk++) {
  156.                         int xx = X[kk][i], yy = Y[kk][i];
  157.                         int idx = getidx(xx,yy);
  158.                         for (int jj = 0; jj < (int)G[idx].size(); jj++) {
  159.                                 int j = G[idx][jj];
  160.                                 for (int k = 0; k < 3; k++) {
  161.                                         frac x = frac(X[k][j]), y = frac(Y[k][j]);
  162.                                         if ((x.p == X[0][i] && y.p == Y[0][i]) ||
  163.                                                 (x.p == X[1][i] && y.p == Y[1][i]) ||
  164.                                                 (x.p == X[2][i] && y.p == Y[2][i])) continue;
  165.                                         if ((x-cx)*(x-cx) + (y-cy)*(y-cy) < r) {
  166.                                                 cout << "NO" << endl;
  167.                                                 return 0;
  168.                                         }
  169.                                 }
  170.                         }
  171.                 }
  172.         }
  173.         cout << "YES" << endl;
  174.         return 0;
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement