长春网站建设及推广,wordpress播放swf插件,私人网站服务器搭建,网站改版影响http://poj.org/problem?id2398 题意大概是说将一个盒子用n个board分成n1 部分 然后往里面放toy,给定盒子,board,和toy的坐标 问所有的toy放完后,有多少部分中有t个toy; 简单计算几何 需要判断的是点和直线的关系. 判断 某一点在直线左右侧 左右方向是相对前进方向的,只要指定… http://poj.org/problem?id2398 题意大概是说将一个盒子用n个board分成n1 部分 然后往里面放toy,给定盒子,board,和toy的坐标 问所有的toy放完后,有多少部分中有t个toy; 简单计算几何 需要判断的是点和直线的关系. 判断 某一点在直线左右侧 左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断. 定义平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量 S(P1,P2,P3)|y1 y2 y3| (x1-x3)*(y2-y3)-(y1-y3)*(x2-x3) 当P1P2P3逆时针时S为正的当P1P2P3顺时针时S为负的。 令矢量的起点为A终点为B判断的点为C 如果SABC为正数则C在矢量AB的左侧 如果SABC为负数则C在矢量AB的右侧 如果SABC为0则C在直线AB上。 /************************************************************************* File Name: code/2015summer/0718/B.cpp Author: 111qqz Email: rkz2013126.com Created Time: 2015年07月18日 星期六 11时58分14秒************************************************************************/
#includeiostream
#includeiomanip
#includecstdio
#includealgorithm
#includecmath
#includecstring
#includestring
#includemap
#includeset
#includequeue
#includevector
#includestack
using namespace std;
#define REP(i, n) for (int i0;iint(n);i)
typedef long long LL;
typedef unsigned long long ULL;
const int N2E35;
struct node
{int x,y;
};
struct node rec,rec2;
struct node par[N],par2[N];
struct node toy[N];
int ans[N],cnt[N];
int n,m;
bool judge(node p1,node p2,node p3) //判断点是否在直线的[右侧!!]
{int s (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if (s0) return false;if (s0) return true;
}
bool cmp(node a,node b)
{if (a.xb.x) return true;if (a.xb.xa.yb.y) return true;return false;
}
int main()
{while (scanf(%d,n)!EOFn){memset(ans,0,sizeof(ans));memset(par,0,sizeof(par));memset(par2,0,sizeof(par2));memset(toy,0,sizeof(toy));cinmrec.xrec.yrec2.xrec2.y;for ( int i 1 ; i n ; i){cinpar[i].xpar2[i].x;par[i].yrec.y;par2[i].yrec2.y;}for ( int i 1 ; i n-1 ; i){for ( int j i1 ; j n ; j){if (par[i].xpar[j].x){swap(par[i].x,par[j].x);// swap(par[i].y,par[j].y);swap(par2[i].x,par2[j].x);// swap(par2[i].y,par2[j].y);}}}
// for ( int i 1 ; i n ; i)
// coutpar[i].xendl;for ( int i 1 ; i m ; i ){cintoy[i].xtoy[i].y;}int p;sort(toy1,toym1,cmp); //如果第i个娃娃在第k个分划中,那么排序后第i1个娃娃至少在第k个分划中....(某大神说过,顺手就能写的优化顺手
// for ( int i 1 ; i m ; i) coutx[i]:toy[i].x y[i]:toy[i].yendl;for ( int i 1 ; i m ; i) {p n 1; //如果在所有board的右侧,那么一定是在最后一个分划中(n个板子形成n1个分划)bool okfalse;for ( int j 1 ; j n ; j){okjudge(par2[j],par[j],toy[i]);if (!ok){// couti:i j:j par2[j].x par2[j].y par[j].x par[j].yendl;p j;break;// cout hhhhhhI:i j:jendl;}}ans[p];}coutBoxendl;memset(cnt,0,sizeof(cnt));for ( int i 1 ; i n1 ; i){if (ans[i]0) continue;cnt[ans[i]];// printf(%d: %d\n,i,ans[i]);}for ( int i 1 ; i m ; i){if (cnt[i]0) continue;printf(%d: %d\n,i,cnt[i]);}}return 0;
} 转载于:https://www.cnblogs.com/111qqz/p/4665640.html
