Red Huang

Red Huang

uva 143

You can use the area method to solve it, remember the precision problem.

Also, if the three points are collinear, you must find the vertex on that line.

//  
//        GGGGGGGGGGGGG        CCCCCCCCCCCCC               AAA  
//     GGG::::::::::::G     CCC::::::::::::C              A:::A  
//   GG:::::::::::::::G   CC:::::::::::::::C             A:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C            A:::::::A  
// G:::::G       GGGGGG C:::::C       CCCCCC           A:::::::::A  
//G:::::G              C:::::C                        A:::::A:::::A  
//G:::::G              C:::::C                       A:::::A A:::::A  
//G:::::G    GGGGGGGGGGC:::::C                      A:::::A   A:::::A  
//G:::::G    G::::::::GC:::::C                     A:::::A     A:::::A  
//G:::::G    GGGGG::::GC:::::C                    A:::::AAAAAAAAA:::::A  
//G:::::G        G::::GC:::::C                   A:::::::::::::::::::::A  
// G:::::G       G::::G C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C   A:::::A             A:::::A  
//   GG:::::::::::::::G   CC:::::::::::::::C  A:::::A               A:::::A  
//     GGG::::::GGG:::G     CCC::::::::::::C A:::::A                 A:::::A  
//        GGGGGG   GGGG        CCCCCCCCCCCCCAAAAAAA                   AAAAAAA  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
using namespace std;  
#ifdef DEBUG  
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);  
#else  
#define debug(...)  
#define gettime()  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp\[htx\]\[hty\]);}Pln();}  
#define M 55  
#define PII pair<int,int\>  
#define PB push\_back  
#define oo INT\_MAX  
#define Set\_oo 0x3f  
#define FOR(it,c) for(vector<PII>::iterator it=(c).begin();it!=(c).end();it++)  
#define eps 1e-6  
clock\_t start\_time=clock(), end\_time;  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
bool xeqy(double x,double y){return fabs(x-y)<eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
struct points{  
    double x,y;  
}p\[3\];  
double maxx,maxy,minx,miny;  
double cal(double x1,double y1,double x2,double y2){  
    return x1\*y2-x2\*y1;  
}  
bool isinside(points o){  
    double area=0;  
    double tarea=fabs(cal(p\[1\].x-p\[0\].x,p\[1\].y-p\[0\].y,p\[2\].x-p\[0\].x,p\[2\].y-p\[0\].y));  
    for(int i=0;i<3;i++){  
        int j=(i+1)%3;  
        area+=fabs(cal(p\[i\].x-o.x,p\[i\].y-o.y,p\[j\].x-o.x,p\[j\].y-o.y));  
//        debug("%.30f %.10f\\n",area,tarea);  
    }  
    if(xeqy(area,tarea)){  
        return true;  
    }  
    return false;  
}  
void solve(){  
    points o;  
    int ans=0;  
    for(int i=ceil(minx);i<=floor(maxx);i++){  
        for(int j=ceil(miny);j<=floor(maxy);j++){  
//            debug("%d %d\\n",i,j);  
            o.x=i;o.y=j;  
            if(isinside(o))ans++;  
        }  
    }  
    printf("%4d\\n",ans);  
}  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    double all=0;  
    while(~scanf("%lf",&p\[0\].x)){  
        scanf("%lf",&p\[0\].y);  
        minx=maxx=p\[0\].x;miny=maxy=p\[0\].y;  
        all=p\[0\].x+p\[0\].y;  
        for(int i=1;i<3;i++){  
            scanf("%lf%lf",&p\[i\].x,&p\[i\].y);  
            minx=min(minx,p\[i\].x);  
            maxx=max(maxx,p\[i\].x);  
            miny=min(miny,p\[i\].y);  
            maxy=max(maxy,p\[i\].y);  
            all+=p\[i\].x+p\[i\].y;  
        }  
        if(all==0)break;  
        minx=max(minx,1.0);  
        miny=max(miny,1.0);  
        maxx=min(maxx,99.0);  
        maxy=min(maxy,99.0);  
        solve();  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.