#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <complex>
#include <memory>
#include <numeric>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <locale.h>

using namespace std;

const int    inf = 0x7f7f7f7f;
const int    INF = 0x7fffffff;
const double eps = 1e-8;
const double  pi = acos(-1.0);

template<class Type> bool scanf(Type & val)
{
    char cin =getchar();
    if(cin==EOF) return false;
    else
    {
        val=0;
        while('0'>cin||cin>'9') if((cin=getchar())==EOF) return false;
        while('0'<=cin&&cin<='9')
        {
            val*=10,val+=(cin-'0');
            if((cin=getchar())==EOF) return false;
        }
        return true;
    }
}

#define _gret(a,b) ((a)-(b)>eps)
#define _less(a,b) ((b)-(a)>eps)
#define _equl(a,b) (fabs((a)-(b))<eps)
#define _sign(val) (_gret(val,0.0)?1:(_equl(val,0.0)?0:-1))

#define _lowbit(val) ((val)&(-val))
#define _max(a,b) (_gret(a,b)?(a):(b))
#define _min(a,b) (_less(a,b)?(a):(b))
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
#define _clr(a,val,n) memset(a,val,sizeof(a[0])*(n))

typedef struct POINTE
{
    double x,y;
    POINTE(double _x=0,double _y=0):x(_x),y(_y){}
};
double det(double x1,double y1,double x2,double y2){return x1*y2-x2*y1;}
double cross(POINTE o,POINTE a,POINTE b){return det(a.x-o.x,a.y-o.y,b.x-o.x,b.y-o.y);}

const int MAXN = 6000;
int n,m,num[MAXN];
double X1,Y1,X2,Y2,U,L,X,Y;
POINTE a[MAXN],b[MAXN];

int main()
{
    while(scanf("%d %d %lf %lf %lf %lf",&n,&m,&X1,&Y1,&X2,&Y2),n)
    {
        a[0]=POINTE(X1,Y1);
        b[0]=POINTE(X1,Y2);
        a[n+1]=POINTE(X2,Y1);
        b[n+1]=POINTE(X2,Y2);
        _for(i,1,n)
        {
            scanf("%lf %lf",&U,&L);
            a[i]=POINTE(U,Y1);
            b[i]=POINTE(L,Y2);
        }
        _clr(num,0,n+1);
        _for(j,0,m-1)
        {
            scanf("%lf %lf",&X,&Y);
            _for(i,0,n)
            {
                double ans=cross(POINTE(X,Y),a[i],b[i])*cross(POINTE(X,Y),a[i+1],b[i+1]);
                if(!_gret(ans,0.0))
                {
                    num[i]++;
                    break;
                }
            }
        }
        _for(i,0,n) printf("%d: %d\n",i,num[i]);
        printf("\n");
    }
    return 0;
}

• 再来个二分的，172MS (2705) speedcell4 2012-01-12 01:49:58
  • 再猥琐一下，double改成longlong，去掉结构体，优化到90+MS (2683) speedcell4 2012-01-12 02:07:47