正文
UVA - 143 Orchard Trees （点在三角形内）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题意：
给出三角形的三个点的坐标（浮点数），
问落在三角形内及三角形边上的整点有多少？
思路：所有点暴力判断（点的范围1-99，三角形可能是0-100，因为这个WA了一下orz）
AC代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const double eps = 1e-;
const double pi = acos(-1.0);
const int maxp = ;
int sgn(double x)
{
if(fabs(x) < eps) return ;
else return x < ? - : ;
}
struct Point{
double x, y;
Point(){}
Point(double _x, double _y){
x = _x, y = _y;
}
void input(){
scanf("%lf%lf", &x, &y);
}
bool operator == (Point b) const{
return sgn(x - b.x) == && sgn(y - b.y) == ;
}
bool operator < (Point b)const{
return sgn(x - b.x) == ? sgn(y - b.y < ) : x < b.x;
}
Point operator - (const Point &b)const{
return Point(x - b.x, y - b.y);
}
//²æ»ý
double operator ^(const Point &b){
return x * b.y - y * b.x;
}
//µã»ý
double operator *(const Point &b){
return x * b.x + y * b.y;
}
double len(){
return hypot(x, y);
}
double len2(){
return x * x + y * y;
}
double distant(Point p){
return hypot(x - p.x, y - p.y);
}
Point operator + (const Point &b)const{
return Point (x + b.x, y + b.y);
}
Point operator * (const double &k)const{
return Point(x * k, y * k);
}
Point operator / (const double &k)const{
return Point(x / k, y / k);
}
};
struct Line{
Point s, e;
Line(){}
Line(Point _s, Point _e){s = _s, e = _e;}
bool operator == (Line v){
return (s == v.s) && (e == v.e);
}
bool pointonseg(Point p){
return sgn((p - s)^(e - s)) == && sgn((p - e)*(p - s)) <= ;
} };
struct polygon{
int n;
Point p[maxp];
Line l[maxp];
void add(Point q){
p[n ++] = q;
}
void input(int _n){
n = _n;
for(int i = ;i < n;i++) p[i].input();
}
void getline(){
for(int i = ;i < n;i++){
l[i] = Line(p[i], p[(i+) % n]);
}
}
int relationpoint(Point q){
for(int i = ;i < n;i++){
if(p[i] == q) return ;
}
getline();
for(int i = ;i < n;i++){
if(l[i].pointonseg(q)) return ;
}
int cnt = ;
for(int i = ;i < n;i++){
int j = (i + ) % n;
int k = sgn((q - p[j])^(p[i] - p[j]));
int u = sgn(p[i].y - q.y);
int v = sgn(p[j].y - q.y);
if(k > && u < && v >= ) cnt++;
if(k < && v < && u >= ) cnt--;
}
return cnt != ;
}
};
int main()
{
double x1, x2, x3, y1, y2, y3;
polygon a;
while(~scanf("%lf%lf%lf%lf%lf%lf",&x1, &y1, &x2, &y2, &x3, &y3) && (x1|| x2|| x3|| y1|| y2|| y3))
{
a.n = ;
a.add(Point(x1,y1));
a.add(Point(x2,y2));
a.add(Point(x3,y3));
int cnt = ;
for(double i = ;i <= ;i++)
for(double j = ;j <= ;j++)
if(a.relationpoint(Point(i,j))) cnt ++;
printf("%4d\n",cnt);
}
return ;
}
