2013
12-21

# 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.

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.

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. Fig.2 shows the positions of ACM particles and the best ICPC position for the last test case in the sample input.

For each test case, output a line containing a single integer, which is the maximum number of dissolved ACM particles.

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

3
3
6

POJ AC_Code 1297MS

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>

#define LL long long
#define EPS (1e-8)

using namespace std;

const double PI = acos(-1.0);

struct P
{
double a;
int x,y,mark;
} pa[1010],p[1010];

double Cal_Angle(P p1,P p2)
{
if(p1.x == p2.x && p1.y == p2.y)
return -100.0;
P v;
v.x = p2.x - p1.x;
v.y = p2.y - p1.y;
if(p1.y <= p2.y)
return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
}

void Cal_Angle(P p,P *pa,int n)
{
for(int i = 0; i < n; ++i)
{
pa[i].a = Cal_Angle(p,pa[i]);
}
}

bool cmp_angle(P p1,P p2)
{
return p1.a < p2.a;
}

int main()
{
int n,i,j,k,l,d;
int Max,tl,tr,b,w,s1,s0,s2,s3;
double xm,pil,pir;
P vec;
while(scanf("%d",&n) && n)
{
b = 0;
w = 0;
for(i = 0; i < n; ++i)
{
scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].mark);
pa[i] = p[i];
if(pa[i].mark)
b++;
else
w++;
}

Max = -1;

for(i = 0; i < n; ++i)
{
Cal_Angle(p[i],pa,n);
sort(pa,pa+n,cmp_angle);

pir = pa[1].a;
pil = pir + PI;

s1 = s0 = s2 = s3 = 0;

for(j = 1; j < n && pa[j].a < pil; ++j)
{
if(pa[j].a == pir)
{
if(pa[j].mark)
s3++;
else
s2++;
}
else
{
if(pa[j].mark)
s1++;
else
s0++;
}
}

for(d = j; d < n && pa[d].a == pil; ++d)
{
if(pa[d].mark)
s3++;
else
s2++;
}

if(pa[0].mark)
s3++;
else
s2++;

tr = s0 + (b-s1)+s2;
tl = s1 + (w-s0)+s3;

if(tr > Max || tl > Max)
Max = tr > tl ? tr : tl;

k = 1;

while(pir < PI && j < n)
{
for(; k < n && pir == pa[k].a; ++k)
{
if(pa[k].mark)
--s3;
else
--s2;
}
pir = pa[k].a;
if(pir > PI)
break;
for(l = k; l < n && pir == pa[l].a; ++l)
{
if(pa[l].mark)
{
++s3;
--s1;
}
else
{
++s2;
--s0;
}
}
for(; j < n && pa[j].a == pil; ++j)
{
if(pa[j].mark)
{
--s3;
++s1;
}
else
{
--s2;
++s0;
}
}

pil = pir+PI;

for(; j < n && pa[j].a < pil; ++j)
{
if(pa[j].mark)
{
++s1;
}
else
{
++s0;
}
}

for(d = j; d < n && pa[d].a == pil ; ++d)
{
if(pa[d].mark)
++s3;
else
++s2;
}
tr = s0 + (b-s1)+s2;
tl = s1 + (w-s0)+s3;
if(tr > Max || tl > Max)
{
Max = tr > tl ? tr : tl;
}
}
}
printf("%d\n",Max);
}
return 0 ;
}

POJ AC_Code 13313MS

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>

#define LL long long
#define EPS (1e-8)

using namespace std;

const double PI = acos(-1);

struct P
{
double x,y,a;
int mark;
}pa[1010],p[1010];

double Cal_Angle(P p1,P p2)
{
if(p1.x == p2.x && p1.y == p2.y)
return -100.0;
P v;
v.x = p2.x - p1.x;
v.y = p2.y - p1.y;
if(p1.y <= p2.y)
return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
}

void Cal_Angle(P p,P *pa,int n)
{
for(int i = 0;i < n; ++i)
{
pa[i].a = Cal_Angle(p,pa[i]);
}
}

bool cmp_angle(P p1,P p2)
{
return p1.a < p2.a;
}

int main()
{
int n,i,j,k;
int tm1,tm0,tm2,tm3,Max,t1,t2,b,w;
double xm,pil,pir;
P vec;
while(scanf("%d",&n) && n)
{
b = 0;
w = 0;
for(i = 0;i < n; ++i)
{
scanf("%lf %lf %d",&p[i].x,&p[i].y,&p[i].mark);
pa[i] = p[i];
if(pa[i].mark)
b++;
else
w++;
}

Max = -1;

for(i = 0;i < n; ++i)
{
Cal_Angle(p[i],pa,n);
sort(pa,pa+n,cmp_angle);
pir = pa[0].a;
j = 1;
while(pir <= PI && j < n)
{
for(;j < n && pa[j].a == pir; ++j)
;
pir = pa[j].a;

tm3 = 0;
tm2 = 0;
tm1 = 0;
tm0 = 0;

for(pil = pir+PI,k = j;pa[k].a < pil && k < n; ++k)
{
if(pa[j].a == pa[k].a)
{
if(pa[k].mark == 1)
{
tm3 ++;
}
else
{
tm2 ++;
}
}
else if(pa[k].mark == 0)
{
tm0++;
}
else
{
tm1++;
}
}
if(pa[0].mark)
tm3++;
else
tm2++;
t1 = tm1+tm2+tm3 + (w-tm0-tm2);
t2 = tm0+tm2+tm3 + (b-tm1-tm3);
if(Max < t1 || Max < t2)
{
Max = t1 > t2 ? t1 : t2;
}
}
}
printf("%d\n",Max);
}
return 0 ;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

2. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;