首页 > 代码库 > POJ 1265

POJ 1265

2024-07-16 16:18:31   218人阅读

主要利用PICK定理与边点数上的GCD的关系求解。

三角形一条边上的所有整数点（包括顶点）可以首先将这条边移到(0, 0)->(x, y)。这时，（x/gcd(x, y), y/gcd(x, y)）肯定在这条边上，并且是整数点，其余所有整数点的可以表示为k(x/gcd(x, y), y/gcd(x, y))。所以所有的整数点个数为gcd(x, y) + 1。即：

b = gcd(x, y) + 1

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAX=110;struct point {	double x,y;}p[MAX];int n;int gcd(int x,int y){	while(y){		int tmp=y;         y = x % y;          x = tmp;      }      return x;}int main(){	int t; int cas=0;	cin>>t;	while(t--){		cas++;		cin>>n;		double tx,ty;		for(int i=0;i<n;i++){			cin>>tx>>ty;			if(i==0){				p[i].x=tx; p[i].y=ty;			}			else{ 				p[i].x=p[i-1].x+tx;				p[i].y=p[i-1].y+ty;			}		}		p[n]=p[0];		double ans=0;		for(int i=0;i<n;i++)		ans+=(p[i].x*p[i+1].y-p[i].y*p[i+1].x);		ans=(ans)/2;		int edg=0,in=0;		for(int i=0;i<n;i++)		edg+=gcd(abs((int)(p[i].x-p[i+1].x)),abs(int(p[i].y-p[i+1].y)));		in=(((ans+1)*2-edg)/2);		printf("Scenario #%d:\n",cas);		printf("%d %d %.1lf\n",in,edg,ans);		printf("\n");	}	return 0;}

　　


联系
我们