UVA - 143 Orchard Trees （点在三角形内）

今天药忘吃喽~ 2023-06-01 11:13 73阅读 0赞

![1696897-20190825000753061-374712109.png][]![1696897-20190825001015561-987595980.png][]

题意：

给出三角形的三个点的坐标（浮点数），  
问落在三角形内及三角形边上的整点有多少？

思路：所有点暴力判断（点的范围1-99，三角形可能是0-100，因为这个WA了一下orz）

AC代码：

1 #include<cstdio>
      2 #include<cmath>
      3 #include<algorithm>
      4 #include<iostream>
      5 #include<cstring>
      6 using namespace std;
      7 typedef long long ll;
      8 const double eps = 1e-8;
      9 const double pi = acos(-1.0);
     10 const int maxp = 5000;
     11 int sgn(double x)
     12 {
     13     if(fabs(x) < eps) return 0;
     14     else return x < 0 ? -1 : 1;
     15 }
     16 struct Point{
     17     double x, y;
     18     Point(){}
     19     Point(double _x, double _y){
     20         x = _x, y = _y;
     21     }
     22     void input(){
     23         scanf("%lf%lf", &x, &y);
     24     }
     25     bool operator == (Point b) const{
     26         return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
     27     }
     28     bool operator < (Point b)const{
     29         return sgn(x - b.x) == 0 ? sgn(y - b.y < 0) : x < b.x;
     30     }
     31     Point operator - (const Point &b)const{
     32         return Point(x - b.x, y - b.y);
     33     }
     34     //²æ»ý
     35     double operator ^(const Point &b){
     36         return x * b.y - y * b.x;
     37     }
     38     //µã»ý
     39     double operator *(const Point &b){
     40         return x * b.x + y * b.y;
     41     }
     42     double len(){
     43         return hypot(x, y);
     44     }
     45     double len2(){
     46     return x * x + y * y;
     47     }
     48     double distant(Point p){
     49         return hypot(x - p.x, y - p.y);
     50     }
     51     Point operator + (const Point &b)const{
     52         return Point (x + b.x, y + b.y);
     53     }
     54     Point operator * (const double &k)const{
     55         return Point(x * k, y * k);
     56     }
     57     Point operator / (const double &k)const{
     58         return Point(x / k, y / k);
     59     }
     60 };
     61 struct Line{
     62     Point s, e;
     63     Line(){}
     64     Line(Point _s, Point _e){s = _s, e = _e;}
     65     bool operator == (Line v){
     66         return (s == v.s) && (e == v.e);
     67     }
     68     bool pointonseg(Point p){
     69         return sgn((p - s)^(e - s)) == 0 && sgn((p - e)*(p - s)) <= 0;
     70     }
     71 
     72 };
     73 struct polygon{
     74     int n;
     75     Point p[maxp];
     76     Line l[maxp];
     77     void add(Point q){
     78         p[n ++] = q;
     79     }
     80     void input(int _n){
     81         n = _n;
     82         for(int i = 0;i < n;i++) p[i].input();
     83     }
     84      void getline(){
     85         for(int i = 0;i < n;i++){
     86             l[i] = Line(p[i], p[(i+1) % n]);
     87         }
     88     }
     89     int relationpoint(Point q){
     90         for(int i = 0;i < n;i++){
     91             if(p[i] == q) return 3;
     92         }
     93         getline();
     94         for(int i = 0;i < n;i++){
     95             if(l[i].pointonseg(q)) return 2;
     96         }
     97         int cnt = 0;
     98         for(int i = 0;i < n;i++){
     99             int j = (i + 1) % n;
    100             int k = sgn((q - p[j])^(p[i] - p[j]));
    101             int u = sgn(p[i].y - q.y);
    102             int v = sgn(p[j].y - q.y);
    103             if(k > 0 && u < 0 && v >= 0) cnt++;
    104             if(k < 0 && v < 0 && u >= 0) cnt--;
    105         }
    106         return cnt != 0;
    107     }
    108 };
    109 int main()
    110 {
    111     double x1, x2, x3, y1, y2, y3;
    112     polygon a;
    113     while(~scanf("%lf%lf%lf%lf%lf%lf",&x1, &y1, &x2, &y2, &x3, &y3) && (x1|| x2|| x3|| y1|| y2|| y3))
    114     {
    115         a.n = 0;
    116         a.add(Point(x1,y1));
    117         a.add(Point(x2,y2));
    118         a.add(Point(x3,y3));
    119         int cnt = 0;
    120         for(double i = 1;i <= 99;i++)
    121             for(double j = 1;j <= 99;j++)
    122                 if(a.relationpoint(Point(i,j))) cnt ++;
    123         printf("%4d\n",cnt);
    124     }
    125     return 0;
    126 }

转载于:https://www.cnblogs.com/Carered/p/11406620.html

[1696897-20190825000753061-374712109.png]: https://img2018.cnblogs.com/blog/1696897/201908/1696897-20190825000753061-374712109.png
[1696897-20190825001015561-987595980.png]: /images/20230601/20b3cacdb8b8411a9d8f1359f958d426.png