Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
皮克定理+GCD分分钟KO!#include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<cstdlib> #include<cmath> const double eps=1e-8; const double PI=3.1415926; const int Max=1001; #define zero(x) (((x)>0?(x):-(x))<eps) using namespace std; int sign(double x) { return (x>eps)-(x<-eps); } typedef struct Node { double x; double y; }point; point list[Max],stack[Max]; int n; int top; double xmult(point p0,point p1,point p2) { return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } double Distance(point p1,point p2)// 返回两点之间欧氏距离 { return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); } bool cmp(point p1,point p2) { double temp; temp=xmult(list[0],p1,p2); if(temp>0) return true; if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2))) return true; return false; } void convex_hull()//凸包模板 { int i; for(i=1;i<n;i++) { point temp; if((list[i].y<list[0].y)||(list[i].y==list[0].y&&list[i].x<list[0].x)) swap(list[0],list[i]); } sort(list+1,list+n,cmp); top=1; stack[0]=list[0]; stack[1]=list[1]; for(i=2;i<n;i++) { while(top>=1&&xmult(stack[top-1],stack[top],list[i])<=0) top--; top++; stack[top]=list[i]; } } int GCD(int x,int y) { return y?GCD(y,x%y):x; } int main() { int m,i,j; int x1,y1,x2,y2,x3,y3; int ax,ay,bx,by,cx,cy; int node_in,node_on,A; while(cin>>x1>>y1>>x2>>y2>>x3>>y3&&(x1||x2||x3||y1||y2||y3)) { node_in=0; node_on=0; A=0; ax=x2-x1; ay=y2-y1; bx=x3-x2; by=y3-y2; cx=x1-x3; cy=y1-y3; node_on+=GCD(abs(ax),abs(ay)); node_on+=GCD(abs(bx),abs(by)); node_on+=GCD(abs(cx),abs(cy)); A+=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1); if(A<0) A=-A; A/=2; //cout<<A<<" "<<node_on<<endl; cout<<(A+1)-node_on/2<<endl; } return 0; } /* 0 0 5 0 0 5 1 1 -2 3 4 -7 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator