Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

皮克定理+GCD分分钟KO!

Posted by ecjtu_yuweiwei at 2014-07-25 20:26:59 on Problem 2954
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator