1010.cpp

ZJU ACM 1010排名第一的程序. 1025的高效程序

#include <stdio.h>

const int N = 1000, L = (1<<10)-1;

double x[N+1], y[N+1], dx[N+1], dy[N+1], d, xd, yd, s, t;
double u[N+1], v[N+1], w[N+1], z[N+1];
char buf[L+1];
bool b[128], sign;
int n, l, len, ch, e;

inline void readbuf() { len=fread(buf,1,L,stdin); buf[len]=l=0; }
int pow10() { int r=1, a=10; while (e) (e&1)?(r*=a,e--):(a*=a,e>>=1); return r; }

int geti() {
  int r=0;
  if (l>=len) readbuf();
  for (e=0; b[ch=buf[l++]]; e++) r=10*r+(ch&0xF);
  if (ch==0) { readbuf(); for (; b[ch=buf[l++]]; e++) r=10*r+(ch&0xF); }
  return r;
}

double getf() {
  double w;
  if (l>=len) readbuf();
  if (buf[l]=='-') sign=1,l++; else sign=0;
  w=geti(); if (ch=='.') w+=(double)geti()/pow10();
  return sign?-w:w;
}

inline void getn() { n=geti(); }
inline void getpoint(int i) { x[i]=getf(); y[i]=getf(); }
inline double det(int i, int j) { return dx[i]*dy[j]-dx[j]*dy[i]; }
inline bool zero(double x) { return ((int)(*(long long*)&x>>52)&0x7FF)<=0x3E1; }

bool sect(int i, int j) {
  if (u[i]>w[j]||u[j]>w[i]||v[i]>z[j]||v[j]>z[i]) return 0;
  if (zero(d=det(i,j))) return 0;
  xd=x[j]-x[i]; yd=y[j]-y[i];
  s=(xd*dy[j]-yd*dx[j])/d; if (s<0||s>1) return 0;
  t=(xd*dy[i]-yd*dx[i])/d; return 0<=t&&t<=1;
}

double area() {
  double a=0.0;
  for (int i=0; i<n; i++) a+=x[i]*y[i+1]-x[i+1]*y[i];
  if (a<0) a=-a;
  return a/2;
}

int main() {
  for (int i='0'; i<='9'; i++) b[i]=1;
  int c=0;
  while (getn(),n!=0) {
    if (c++) putchar('\n');
    for (int i=0; i<n; i++) getpoint(i); x[n]=x[0]; y[n]=y[0];
    for (int i=0; i<n; i++) {
      dx[i]=x[i+1]-x[i]; dy[i]=y[i+1]-y[i];
      if (dx[i]<0) u[i]=x[i+1],w[i]=x[i]; else w[i]=x[i+1],u[i]=x[i];
      if (dy[i]<0) v[i]=y[i+1],z[i]=y[i]; else z[i]=y[i+1],v[i]=y[i];
    }
    if (n<3||n==3&&zero(det(0,2))) goto next;
    for (int j=n-2; j>1; j--) if (sect(0,j)) goto next;
    for (int i=n-3; i>0; i--) for (int j=i+2; j<n; j++) if(sect(i,j)) goto next;
    printf("Figure %d: %.2lf\n",c,area()); continue;
    next: printf("Figure %d: Impossible\n",c);
  }
  return 0;
}