第四十五题 UVA1606 两亲性分子 Amphiphilic Carbon Molecules 待评测
Shanghai Hypercomputers, the world’s largest computer chip manufacturer, has invented a new class
of nanoparticles called Amphiphilic Carbon Molecules (ACMs). ACMs are semiconductors. It means
that they can be either conductors or insulators of electrons, and thus possess a property that is very
important for the computer chip industry. They are also amphiphilic molecules, which means parts
of them are hydrophilic while other parts of them are hydrophobic. Hydrophilic ACMs are soluble
in polar solvents (for example, water) but are insoluble in nonpolar solvents (for example, acetone).
Hydrophobic ACMs, on the contrary, are soluble in acetone but insoluble in water. Semiconductor
ACMs dissolved in either water or acetone can be used in the computer chip manufacturing process.
Fig.1
As a materials engineer at Shanghai
Hypercomputers, your job is to prepare
ACM solutions from ACM particles. You
go to your factory everyday at 8 am and
find a batch of ACM particles on your
workbench. You prepare the ACM solutions by dripping some water, as well
as some acetone, into those particles and
watch the ACMs dissolve in the solvents.
You always want to prepare unmixed solutions, so you first separate the ACM particles by placing an Insulating Carbon Partition Card (ICPC) perpendicular to your
workbench. The ICPC is long enough to
completely separate the particles. You then drip water on one side of the ICPC and acetone on the
other side. The ICPC helps you obtain hydrophilic ACMs dissolved in water on one side and hydrophobic ACMs dissolved in acetone on the other side. If you happen to put the ICPC on top of some ACM
particles, those ACMs will be right at the border between the water solution and the acetone solution,
and they will be dissolved. Fig.1 shows your working situation.
Your daily job is very easy and boring, so your supervisor makes it a little bit more challenging by
asking you to dissolve as much ACMs into solution as possible. You know you have to be very careful
about where to put the ICPC since hydrophilic ACMs on the acetone side, or hydrophobic ACMs on
the water side, will not dissolve. As an experienced engineer, you also know that sometimes it can be
very difficult to find the best position for the ICPC, so you decide to write a program to help you. You
have asked your supervisor to buy a special digital camera and have it installed above your workbench,
so that your program can obtain the exact positions and species (hydrophilic or hydrophobic) of each
ACM particle in a 2D pictures taken by the camera. The ICPC you put on your workbench will appear
as a line in the 2D pictures.
Input
There will be no more than 10 test cases. Each case starts with a line containing an integer N, which
is the number of ACM particles in the test case. N lines then follow. Each line contains three integers
x, y, r, where (x, y) is the position of the ACM particle in the 2D picture and r can be 0 or 1, standing
for the hydrophilic or hydrophobic type ACM respectively. The absolute value of x, y will be no larger
than 10000. You may assume that N is no more than 1000. N = 0 signifies the end of the input and
need not be processed.
Output
For each test case, output a line containing a single integer, which is the maximum number of dissolved
ACM particles.
Note: Fig.2 shows the positions of ACM particles and the best ICPC position for the last test case in
the sample input.
Fig.2
Sample Input
3
0 0 0
0 1 0
2 2 1
4
0 0 0
0 4 0
4 0 0
1 2 1
7
-1 0 0
1 2 1
2 3 0
2 1 1
0 3 1
1 4 0
-1 2 0
0
Sample Output
3
3
6
关于本题目 ：判断点在直线的哪一侧
方法一：
采用几何计算，求面积法。转载：http://blog.csdn.net/modiz/article/details/9928955
注意向量是有方向的…
判断 某一点在直线左右侧
左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断.
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
（本体中的P3就是坐标原点）
S(P1,P2,P3)=|y1 y2 y3|= (x1-x3)(y2-y3)-(y1-y3)(x2-x3)
当P1 P2 P3逆时针时S为正的，当P1 P2 P3顺时针时S为负的。
令矢量的起点为A，终点为B，判断的点为C，
如果S（A，B，C）为正数，则C在矢量AB的左侧；
如果S（A，B，C）为负数，则C在矢量AB的右侧；
如果S（A，B，C）为0，则C在直线AB上。
[其实就是向量积（叉积）]
方法二：
采用向量叉积方式：转载http://blog.csdn.net/modiz/article/details/9928553
它可以用来判断点在直线的某侧。进而可以解决点是否在三角形内，两个矩形是否重叠等问题。向量的叉积的模表示这两个向量围成的平行四边形的面积。
设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P×Q = x1y2 - x2y1，其结果是一个伪矢量。
显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。
叉积的方向与进行叉积的两个向量都垂直，所以叉积向量即为这两个向量构成平面的法向量。
如果向量叉积为零向量，那么这两个向量是平行关系。
因为向量叉积是这两个向量平面的法向量，如果两个向量平行无法形成一个平面，其对应也没有平面法向量。所以，两个向量平行时，其向量叉积为零。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define Maxn 1005
using namespace std;
struct Node{
int x,y;
double rad;
bool operator < (const Node &u) const {
return rad < u.rad;
}
}p[Maxn],op[Maxn];
int colr[Maxn],n;
inline bool Is_lef(Node a,Node b) { return a.x * b.y - a.y * b.x >= 0; }
// Is_lef 判断点b是否在点(0,0)和点a连线的左侧 没看懂的去看计算几何
int Solve() {
int Ans = 0;
for(int i=1; i<=n; i++) {
// i枚举基准点
int k = 0;
for(int j=1; j<=n; j++)
if(i != j){
p[k].x = op[j].x - op[i].x;
p[k].y = op[j].y - op[i].y;
if(colr[j]) { p[k].x *= -1; p[k].y *= -1; }
p[k].rad = atan2(p[k].y,p[k].x);
k++;
}
sort(p, p + k);
int L = 0,R = 0,cnt = 2;
while(L < k) {
if(L == R) { R = (R + 1) % k; ++cnt; }
while(L != R && Is_lef(p[L], p[R]) ) { R = (R + 1) % k; ++cnt; }
--cnt;
++L;
Ans = max(Ans,cnt);
}
}
return Ans;
}
int main(int argc,char* argv[]) {
while(scanf("%d",&n) == 1 && n) {
for(int i=1; i<=n; i++)
scanf("%d%d%d",&op[i].x,&op[i].y,&colr[i]);
printf("%d\n",Solve());
}
return 0;
}