vec vsq[] = {	{0,0}, {10,0}, {10,10}, {0,10},
			{2.5,2.5}, {7.5,0.1}, {7.5,7.5}, {2.5,7.5}};
 
polygon_t sq = { 4, vsq }, /* outer square */
sq_hole = { 8, vsq };      /* outer and inner square, ie hole */COPY

use IO::Handle;
STDOUT->autoflush(1);
 
my $coordfile="a.txt";
my @poly=(
    96.802,87.23,
    89.094,78.623,
    92.268,64.808,
    115.391,61.863,
    124.913,77.265,
    115.845,90.174,
    102.696,92.439,
    #96.802,87.23,
);
 
our @V;
my $i=0;
while (scalar(@poly)>0) {
    $V[$i]{x}=shift @poly;
    $V[$i]{y}=shift @poly;
    $i++;
}
 
my ($x, $y);
my %dot;
open READ,"<",$coordfile or die "$!";
open INPOLY, ">", "inside.txt" or die;
open OUTPOLY, ">", "outside.txt" or die ;
foreach (<READ>) {
    ($x, $y, undef) = split(/ |,/, $_);
    #print $x," , ",$y,"\n";
    $dot{x} = $x;
    $dot{y} = $y;
 
    if (&pointInPolygon(\%dot) eq "true") {
        print INPOLY "$x, $y\r\n";
        print "($x, $y) in polygon\n";
    } else {
        print OUTPOLY "$x, $y\r\n";
    }
}
close READ;
close INPOLY;
close OUTPOLY;
 
sub pointInPolygon {
    our @V;
    my $p = shift;
    my $npoints = $#V+1;
    my ($low, $high) = (0, $npoints);
    do {
        $mid = ($low + $high) / 2;
        $mid=int($mid)+1 if ($mid > int($mid));
        if ( &TriangleIsCCW($V[0], $V[$mid], $p) eq "true" ) {
            $low = $mid;
        } else {
            $high = $mid;
        }
    } while ( ($low + 1) < $high);
 
    if( ($low == 0) or ($high == $npoints) ) {
        #print "$npoints $low $mid $high\n";
        return "false";
    }
    return &TriangleIsCCW($V[$low], $V[$high], $p);
}
 
sub TriangleIsCCW {
    my ($p0, $p1, $p2) = @_;
    my $cross;
    my ($d0, $d1, $d2, $d3);
    $d0 = ($p1->{x} - $p0->{x});
    $d1 = ($p1->{y} - $p0->{y});
    $d2 = ($p2->{x} - $p0->{x});
    $d3 = ($p2->{y} - $p0->{y});
 
    $cross = &Cross($d0, $d1, $d2, $d3);
    if ($cross > 0) {
        return "true";
    } else {
        return "false";
    }
}
 
sub Cross {
    #T Cross(T x0, T y0, T x1, T y1) {
    #//|x0 y0| = |a b|
    #//|x1 y1|   |c d|
    #//ad * bc
    #//x0 * y1 - x1 * y0
    my ($x0, $y0, $x1, $y1) = @_;
    my $result;
    $result = ($x0 * $y1) - ($y0 * $x1);
    return $result;
}COPY

my $result;
$result = ($x0 * $y1) - ($y0 * $x1);
return $result;COPY

($x0 * $y1) - ($y0 * $x1);COPY

template<class T>
bool triangleIsCCW(
	T x0, T y0,
	T x1, T y1,
	T x2, T y2) {
	auto cross = -(Cross<T>(x1-x0,y1-y0,x2-x0,y2-y0));
	return cross > 0;
}COPY

#include <stdio.h>
#define bool int
#define false 0
#define true 1
 
typedef struct {
	float x;
	float y;
} Point;
 
Point poly[]={
    96.802,87.23,
    89.094,78.623,
    92.268,64.808,
    115.391,61.863,
    124.913,77.265,
    115.845,90.174,
    102.696,92.439,
};
 
float Cross(
    float x0, float y0, 
    float x1, float y1
) {
    return (x0 * y1) - (x1 * y0);
}
 
int triangleIsCCW( //判断三个点的顺序是否为逆时针
    Point P0, Point P1, Point P2
) {
    auto cross = (
        Cross(
            P1.x-P0.x, P1.y-P0.y,
            P2.x-P0.x, P2.y-P0.y
        )
    );
    return cross >= 0;
}
 
bool pointInPolygon(
    Point vip, Point poly[], int n_poly
) {
    // points represented by [(x0,y0), ... (xn,yn)]
    int low = 0,  high = n_poly;
    int mid;
    do {
        mid = (low + high) / 2;
        if ( 
            triangleIsCCW(poly[0], poly[mid], vip) 
        ) {
            low = mid;
        } else {
            high = mid;
        }
    } while (low + 1 < high);
    if (low == 0 || high == n_poly) return false;
    return triangleIsCCW(poly[low], poly[high], vip);
}
 
int main(int argc, char *argv[]) 
{
    FILE *fp = fopen("a.txt","r");
    FILE *wrt = fopen("inside.txt","w");
    Point vip;
    char s[1024];
	int n_poly = (sizeof(poly) / sizeof(poly[0].x)) / 2;
	int in_polygon;
    while ( ! feof(fp) ) {
        fgets(s, 1024, fp);
        if ( sscanf(s, "%f %f", &vip.x, &vip.y) < 2 ) {
            sscanf(s, "%f,%f", &vip.x, &vip.y);
        }
        in_polygon = pointInPolygon(vip, poly, n_poly);
        if ( in_polygon ) {
            printf("%.3f, %.3f\n", vip.x, vip.y);
            fprintf(wrt, "%.3f, %.3f\n", vip.x, vip.y);
        }
    }
    fclose(fp);
    fclose(wrt);
    return 0;
}COPY