[Login|Register]
New post

Show post

Search forum

Read post
Re:有谁能提供一些测试数据么。。 [ Topic ] 2009-09-08 21:08:49 brother_yan
#include<iostream>
using namespace std;

class point
{
  public:
    double x;
    double y;
};

double s(point o,point a,point b)//三角形的有向面积
{
  return(((a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y))/2);
}

int main()
{
  point p[60];
  int n,m;
 
  while (cin>>n>>m&&n!=0)
    {
      point temp;
      int i;
     
      for (i=1; i<=n; ++i)
        cin>>p[i].x>>p[i].y;
       
      int sum=0;
      for (i=1; i<=m; ++i)
        {
          cin>>temp.x>>temp.y;
         
          int j;
          bool out=false;
         
          for (j=1; j<=n-2; ++j)
            if (s(p[n],p[j],p[j+1])*s(temp,p[j],p[j+1])<0)
              out=true;
          if (s(p[1],p[n-1],p[n])*s(temp,p[n-1],p[n])<0)
            out=true;
          if (s(p[2],p[1],p[n])*s(temp,p[1],p[n])<0)
            out=true;
         
          if (out) sum+=1;
          else sum+=2;
        }
      cout<<sum<<endl;
    }
   
  return(0);
}
Reply
Title
Message
(64K)
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.9ms with 2 query(s).