洛阳网站建设/比较有名的个人网站

看到这道题我就想起了怎样求任意多边形面积,方法是沿着多边形叉积一圈加和取绝对值减半.
还记得证明是将每一条边的两个端点向下做垂线,得到$n$个梯形,这些梯形面积有正有负,最后加加减减的就得到多边形面积辣.
于是这道题完全可以按照那个方法求面积嘛
$n\le100$,所以$n^3$不会超时
我本来以为这只算个暴力,但是在网上找了找,貌似叫梯形剖分?SMG?
总之可能还可以有些小优化吧,但总体复杂度是不变的
还有就是注意精度问题QAQ,浮点运算一定要注意精度问题

/****************************************\
* Author : ztx
* Title  : [bzoj] 3635: Neerc2006 ASCII Art
* ALG    : 计算几何
* CMT    : 
* Time   : 
\****************************************/#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef long double lf ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;if (CH == '-') NEG = true , CH = getchar() ;while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {while (ret=getchar() , ret<'!') ;while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {ret[0]=0;while (CH=getchar() , CH<'!') ;while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;ret[ret[0]+1]=0;
}#define  maxn  110LL
#define  eps  1E-13inline int sign(lf x) { return (x>eps)-(x<-eps) ; }struct P {int x , y ;inline void in() { read(x) , read(y) ; }
} points[maxn] , tmp ;int n , R , C ;
lf a[maxn][maxn] = {0} ;
lf K[maxn] , B[maxn] ;inline void GetKB(int i,P a,P b) {if (a.x==b.x || a.y==b.y) return ;K[i] = (lf)(a.y-b.y)/(lf)(a.x-b.x) ;B[i] = (lf)a.y-K[i]*a.x ;
}inline lf GetY(int i,int X) { return K[i]*X+B[i] ; }
inline lf GetX(int i,int Y) { return (Y-B[i])/K[i] ; }template<typename Tp> inline void Exchange(Tp&a,Tp&b){Tp c=a;a=b;b=c;}lf left , right , mid1 , mid2 ;
inline lf Judge(int i,P a,P b,int r,int c) {if (a.x == b.x) return 0 ;left = GetY(i,c-1) , right = GetY(i,c) ;mid1 = GetX(i,r) , mid2 = GetX(i,r-1) ;if (left < right) {Exchange(left,right) ;mid1 = c*2.0-1.0-mid1 ;mid2 = c*2.0-1.0-mid2 ;}if (a.x < b.x) {/* positive */if (a.x>=c || b.x<c) return 0 ;if (a.y == b.y) return a.y<r ? 0 : 1 ;if (sign(left-(r-1.0))<=0 && sign(right-(r-1.0))<=0) return 0 ;if (sign(left-r)>=0 && sign(right-r)>=0) return 1 ;if (left >= r) {if (sign(right-(r-1.0))>=0) return 1.0-(c-mid1)*(r-right)/2.0 ;return (mid1+mid2)/2.0-(c-1.0) ;} else {if (sign(right-(r-1.0))>=0) return (left+right)/2.0-(r-1.0) ;return (left-(r-1.0))*(mid2-(c-1.0))/2.0 ;}} else {/* negative */Exchange(a,b) ;if (a.x>=c || b.x<c) return 0 ;if (a.y == b.y) return a.y<r ? 0 : -1 ;if (sign(left-(r-1.0))<=0 && sign(right-(r-1.0))<=0) return 0 ;if (sign(left-r)>=0 && sign(right-r)>=0) return -1 ;if (left >= r) {if (sign(right-(r-1.0))>=0) return (c-mid1)*(r-right)/2.0-1.0 ;return (c-1.0)-(mid1+mid2)/2.0 ;} else {if (sign(right-(r-1.0))>=0) return (r-1.0)-(left+right)/2.0 ;return -(left-(r-1.0))*(mid2-(c-1.0))/2.0 ;}}
}int main() {
int i , j , k ;
//  #define READ#ifdef  READfreopen("data.in" ,"r",stdin ) ;freopen("data.out","w",stdout) ;#endifread(n) , read(C) , read(R) ;Rep (i,1,n) points[i].in() ;points[0] = points[n] ;Rep (i,1,n) GetKB(i,points[i-1],points[i]) ;Rep (i,1,R) Rep (j,1,C) {Rep (k,1,n) {a[i][j] += Judge(k,points[k-1],points[k],i,j) ;}}Rev (i,R,1) {Rep (j,1,C) {if (sign(a[i][j]-0.5)<0) {if (sign(a[i][j]-0.25)<0) putchar('.') ;else putchar('+') ;} else {if (sign(a[i][j]-0.75)<0) putchar('o') ;else if (sign(a[i][j]-1.0)<0) putchar('$') ;else putchar('#') ;}}puts("") ;}#ifdef  READfclose(stdin) ; fclose(stdout) ;#elsegetchar() ; getchar() ;#endifreturn 0 ;
}