ACM_Notebook_new

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ngthanhtrung23/ACM_Notebook_new

:warning: Geometry/voronoi.cpp

Code

// Source: http://web.mit.edu/~ecprice/acm/acm08/notebook.html#file7
#define MAXN 1024
#define INF 1000000

//Voronoi diagrams: O(N^2*LogN)
//Convex hull: O(N*LogN)
typedef struct {
  int id;
  double x;
  double y;
  double ang;
} chp;

int n;
double x[MAXN], y[MAXN]; // Input points
chp inv[2*MAXN]; // Points after inversion (to be given to Convex Hull)
int vors;
int vor[MAXN]; // Set of points in convex hull; 
               //starts at lefmost; last same as first!!
PT ans[MAXN][2];

int chpcmp(const void *aa, const void *bb) {
  double a = ((chp *)aa)->ang;
  double b = ((chp *)bb)->ang;
  if (a<b) return -1;
  else if (a>b) return 1;
  else return 0; // Might be better to include a 
                 // tie-breaker on distance, instead of the cheap hack below
}

int orient(chp *a, chp *b, chp *c) {
  double s = a->x*(b->y-c->y) + b->x*(c->y-a->y) + c->x*(a->y-b->y);
  if (s>0) return 1;
  else if (s<0) return -1;
  else if (a->ang==b->ang && a->ang==c->ang) return -1; // Cheap hack 
           //for points with same angles
  else return 0;
}

//the pt argument must have the points with precomputed angles (atan2()'s)
//with respect to a point on the inside (e.g. the center of mass)
int convexHull(int n, chp *pt, int *ans) {
  int i, j, st, anses=0;

  qsort(pt, n, sizeof(chp), chpcmp);
  for (i=0; i<n; i++) pt[n+i] = pt[i];
  st = 0;
  for (i=1; i<n; i++) { // Pick leftmost (bottommost) 
                        //point to make sure it's on the convex hull
    if (pt[i].x<pt[st].x || (pt[i].x==pt[st].x && pt[i].y<pt[st].y)) st = i;
  }
  ans[anses++] = st;
  for (i=st+1; i<=st+n; i++) {
    for (j=anses-1; j; j--) {
      if (orient(pt+ans[j-1], pt+ans[j], pt+i)>=0) break;
      // Should change the above to strictly greater,
      // if you don't want points that lie on the side (not on a vertex) of the hull
      // If you really want them, you might also put an epsilon in orient
    }
    ans[j+1] = i;
    anses = j+2;
  }
  for (i=0; i<anses; i++) ans[i] = pt[ans[i]].id;
  return anses;
}

int main(void) {
  int i, j, jj;
  double tmp;

  scanf("%d", &n);
  for (i=0; i<n; i++) scanf("%lf %lf", &x[i], &y[i]);
  for (i=0; i<n; i++) {
    x[n] = 2*(-INF)-x[i]; y[n] = y[i];
    x[n+1] = x[i]; y[n+1] = 2*INF-y[i];
    x[n+2] = 2*INF-x[i]; y[n+2] = y[i];
    x[n+3] = x[i]; y[n+3] = 2*(-INF)-y[i];
    for (j=0; j<n+4; j++) if (j!=i) {
      jj = j - (j>i);
      inv[jj].id = j;
      tmp = (x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]);
      inv[jj].x = (x[j]-x[i])/tmp;
      inv[jj].y = (y[j]-y[i])/tmp;
      inv[jj].ang = atan2(inv[jj].y, inv[jj].x);
    }
    vors = convexHull(n+3, inv, vor);
    // Build bisectors
    for (j=0; j<vors; j++) {
      ans[j][0].x = (x[i]+x[vor[j]])/2;
      ans[j][0].y = (y[i]+y[vor[j]])/2;
      ans[j][1].x = ans[j][0].x - (y[vor[j]]-y[i]);
      ans[j][1].y = ans[j][0].y + (x[vor[j]]-x[i]);
    }
    printf("Around (%lf, %lf)\n", x[i], y[i]);
    // List all intersections of the bisectors
    for (j=1; j<vors; j++) {
      PT vv;
      vv = ComputeLineIntersection(ans[j-1][0], ans[j-1][1],
				   ans[j][0], ans[j][1]);
      printf("%lf, %lf\n", vv.x, vv.y);
    }
    printf("\n");
  }
  return 0;
}
#line 1 "Geometry/voronoi.cpp"
// Source: http://web.mit.edu/~ecprice/acm/acm08/notebook.html#file7
#define MAXN 1024
#define INF 1000000

//Voronoi diagrams: O(N^2*LogN)
//Convex hull: O(N*LogN)
typedef struct {
  int id;
  double x;
  double y;
  double ang;
} chp;

int n;
double x[MAXN], y[MAXN]; // Input points
chp inv[2*MAXN]; // Points after inversion (to be given to Convex Hull)
int vors;
int vor[MAXN]; // Set of points in convex hull; 
               //starts at lefmost; last same as first!!
PT ans[MAXN][2];

int chpcmp(const void *aa, const void *bb) {
  double a = ((chp *)aa)->ang;
  double b = ((chp *)bb)->ang;
  if (a<b) return -1;
  else if (a>b) return 1;
  else return 0; // Might be better to include a 
                 // tie-breaker on distance, instead of the cheap hack below
}

int orient(chp *a, chp *b, chp *c) {
  double s = a->x*(b->y-c->y) + b->x*(c->y-a->y) + c->x*(a->y-b->y);
  if (s>0) return 1;
  else if (s<0) return -1;
  else if (a->ang==b->ang && a->ang==c->ang) return -1; // Cheap hack 
           //for points with same angles
  else return 0;
}

//the pt argument must have the points with precomputed angles (atan2()'s)
//with respect to a point on the inside (e.g. the center of mass)
int convexHull(int n, chp *pt, int *ans) {
  int i, j, st, anses=0;

  qsort(pt, n, sizeof(chp), chpcmp);
  for (i=0; i<n; i++) pt[n+i] = pt[i];
  st = 0;
  for (i=1; i<n; i++) { // Pick leftmost (bottommost) 
                        //point to make sure it's on the convex hull
    if (pt[i].x<pt[st].x || (pt[i].x==pt[st].x && pt[i].y<pt[st].y)) st = i;
  }
  ans[anses++] = st;
  for (i=st+1; i<=st+n; i++) {
    for (j=anses-1; j; j--) {
      if (orient(pt+ans[j-1], pt+ans[j], pt+i)>=0) break;
      // Should change the above to strictly greater,
      // if you don't want points that lie on the side (not on a vertex) of the hull
      // If you really want them, you might also put an epsilon in orient
    }
    ans[j+1] = i;
    anses = j+2;
  }
  for (i=0; i<anses; i++) ans[i] = pt[ans[i]].id;
  return anses;
}

int main(void) {
  int i, j, jj;
  double tmp;

  scanf("%d", &n);
  for (i=0; i<n; i++) scanf("%lf %lf", &x[i], &y[i]);
  for (i=0; i<n; i++) {
    x[n] = 2*(-INF)-x[i]; y[n] = y[i];
    x[n+1] = x[i]; y[n+1] = 2*INF-y[i];
    x[n+2] = 2*INF-x[i]; y[n+2] = y[i];
    x[n+3] = x[i]; y[n+3] = 2*(-INF)-y[i];
    for (j=0; j<n+4; j++) if (j!=i) {
      jj = j - (j>i);
      inv[jj].id = j;
      tmp = (x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]);
      inv[jj].x = (x[j]-x[i])/tmp;
      inv[jj].y = (y[j]-y[i])/tmp;
      inv[jj].ang = atan2(inv[jj].y, inv[jj].x);
    }
    vors = convexHull(n+3, inv, vor);
    // Build bisectors
    for (j=0; j<vors; j++) {
      ans[j][0].x = (x[i]+x[vor[j]])/2;
      ans[j][0].y = (y[i]+y[vor[j]])/2;
      ans[j][1].x = ans[j][0].x - (y[vor[j]]-y[i]);
      ans[j][1].y = ans[j][0].y + (x[vor[j]]-x[i]);
    }
    printf("Around (%lf, %lf)\n", x[i], y[i]);
    // List all intersections of the bisectors
    for (j=1; j<vors; j++) {
      PT vv;
      vv = ComputeLineIntersection(ans[j-1][0], ans[j-1][1],
				   ans[j][0], ans[j][1]);
      printf("%lf, %lf\n", vv.x, vv.y);
    }
    printf("\n");
  }
  return 0;
}
Back to top page