这题用到了pick公式,area=on/2+in-1 on为在多边形边上的点数,in为在多边形内的点数。叉积求多边形面积,gcd(x,y)为边上的点数,x为相邻两点x差的绝对值,y同理。根据公式可求在多边形内的点数。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int ab(int a) { return a>=0?a:-a; } int main() { int x[3],y[3]; while(cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2],!(!x[0]&&!x[1]&&!x[2]&&!y[0]&&!y[1]&&!y[2])) { int ep=0,area=0,in; for(int i=0; i<3; i++) area+=x[i]*y[(i+1)%3]-y[i]*x[(i+1)%3], ep+=gcd(ab(x[i]-x[(i+1)%3]),ab(y[i]-y[(i+1)%3])); area=ab(area); in=area/2-ep/2+1; printf("%d\n",in); } return 0; }