实际上，模板缓冲区与深度缓冲区是共用一个“物理缓冲区”的，即真正存在的只有一个缓冲区，该缓冲区中任一像素处保存了两种信息：深度值与模板值。比如一个像素占用4个字节（32位），那么深度值可能占用前面几位，模板值占用后面几位。在D3D11中针对该缓冲区，定义了如下几种数据格式：
DXGI_FORMAT_D32_FLOAT_S8X24_UINT：该格式中，每个像素为8字节（64位），其中深度值占32位，为float型。模板值为8位，为位于[0,255]中的整型，后面24位无任何用途，纯对齐用；
DXGI_FORMAT_D24_UNORM_S8_UINT：该格式中，每个像素为4字节（32位），其中深度值占24位，并映射到[0,1]之间。模板值为8位，为位于[0,255]中的整型；
在大多数情况下，我们使用第二种格式，在我们前面所有的示例程序中，使用的正是这种格式。在初始化D3D时，我们需要在创建深度/模板缓冲区时为它指定相应的格式，对应代码如下（对应 dsDesc.Format部分）：
D3D11_TEXTURE2D_DESC dsDesc;
dsDesc.Format = DXGI_FORMAT_D24_UNORM_S8_UINT;
dsDesc.Width = m_clientWidth;
dsDesc.Height = m_clientHeight;
dsDesc.BindFlags = D3D11_BIND_DEPTH_STENCIL;
dsDesc.MipLevels = 1;
dsDesc.ArraySize = 1;
dsDesc.CPUAccessFlags = 0;
dsDesc.SampleDesc.Count = g_x4MsaaQuality<1?1:4;
dsDesc.SampleDesc.Quality = g_x4MsaaQuality<1?0:g_x4MsaaQuality-1;
dsDesc.MiscFlags = 0;
dsDesc.Usage = D3D11_USAGE_DEFAULT;
hr = m_d3dDevice->CreateTexture2D(&dsDesc,0,&m_depthStencilBuffer);
if(FAILED(hr))
{
MessageBox(NULL,_T("Create depth stencil buffer failed!"),_T("ERROR"),MB_OK);
return false;
}
hr = m_d3dDevice->CreateDepthStencilView(m_depthStencilBuffer,0,&m_depthStencilView);
if(FAILED(hr))
{
MessageBox(NULL,_T("Create depth stencil view failed!"),_T("ERROR"),MB_OK);
return false;
}
m_deviceContext->OMSetRenderTargets(1,&m_renderTargetView,m_depthStencilView);
2. 模板判断依据
正如深度缓冲区使用片段的深度值作为判断该片段是否通过的依据，模板缓冲区也有它独特的判断依据，如以下公式所示：
该判断主要包含两部分：COMPARISON左边部分和右边部分。
StencilRef为程序员设定的一个参考值，StencilReadMask为模板值读取掩码，与参考值“按位与”作为式子中的左边的结果；一般情况下，我们设定该掩码为0xFF，即接位与的结果就是模板参考值本身；
Value为模板缓冲区中对应位置处的当前值，同样与掩码按位与后作为右边的结果值；
式子中左、右两部分的结果通过中间的比较操作“COMPARISON”来决定决断的结果，在D3D11中，比较操作定义为如下枚举类型：
typedef enum D3D11_COMPARISON_FUNC {
D3D11_COMPARISON_NEVER = 1,
D3D11_COMPARISON_LESS = 2,
D3D11_COMPARISON_EQUAL = 3,
D3D11_COMPARISON_LESS_EQUAL = 4,
D3D11_COMPARISON_GREATER = 5,
D3D11_COMPARISON_NOT_EQUAL = 6,
D3D11_COMPARISON_GREATER_EQUAL = 7,
D3D11_COMPARISON_ALWAYS = 8
} D3D11_COMPARISON_FUNC;
通过名字即很容易想到其意义，我们忽略前缀：
NEVER：判断操作永远失败，即片段全部不通过模板测试；
LESS：该判断为“<"操作，即左边<右边时测试通过；
EQUAL：“=”操作，即当左、右两边相等时测试通过；
LESS_EQUAL：“<="操作，当左边<=右边时测试通过；
GREATER：">"操作，当左边>右边时测试通过；
NOT_EQUAL："!="操作，当左、右两边不相等时测试通过；
GREATER_EQUAL：">="操作，当左边>=右边时测试通过；
ALWAYS：永远通过，即不管左右两边的值，恒通过。
这里的枚举类型同样适应于深度缓冲区中比较操作的设定。
举个例子说明下模板测试的过程：
比如我们设定模板参考值为1，掩码值为0xffffffff，针对某个片段，如果模板缓冲区中对应的当前模板值为0，则按上述公式，
左边 = 1 & 0xFF = 1；
右边 = 0 & 0xFF = 0；
1. 如果比较操作我们设定为ALWAYS，则该片段的模板测试通过（不管左右两边什么值）；
2. 如果比较操作我们设定为LESS，则由于1 < 0是错误的，因此该片段的模板测试失败，片段被丢弃；
3. 如果比较操作我们设定为GREATER，由于1 > 0正确，因此模板测试成功，片段通过。
其他比较操作依次类推，很简单。
在上一步骤中的模板测试之后，不管片段是否通过测试，都要对模板缓冲区进行相应的更新。至于怎么更新，取决于程序员的设定。D3D11中针对模板缓冲区的更新操作定义了如下枚举类型：
typedef enum D3D11_STENCIL_OP {
D3D11_STENCIL_OP_KEEP = 1,
D3D11_STENCIL_OP_ZERO = 2,
D3D11_STENCIL_OP_REPLACE = 3,
D3D11_STENCIL_OP_INCR_SAT = 4,
D3D11_STENCIL_OP_DECR_SAT = 5,
D3D11_STENCIL_OP_INVERT = 6,
D3D11_STENCIL_OP_INCR = 7,
D3D11_STENCIL_OP_DECR = 8
} D3D11_STENCIL_OP;
同样，我们忽略前缀：
KEEP：保持当前值 不变，比如测试前模板值为0，则继续为0不变；
ZERO：把模板缓冲区对应位置的模板值设为0；
REPLACE："replace"即替换的意思，即使用模板参考值替换模板缓冲区中对应的当前值；
INCR_SAT："INCR"即increase，自增的意思，"SAT"为saturate，用于限制自增的范围。即把当前的模板值加1。如果值超过了255（因为我们的模板缓冲区为8位，因此255即为最大值），则保持在255。
DECR_SAT：同上，DECR为"decrease"，自减的意思，即把当前值自减1，如果值低于0，则保持在0；
INVERT：把当前模板值按位取反。比如对于0xffffffff，更新后的结果为0x00000000；
INCR：同上面的INCR一样，也是把当前模板值自增1，但如果值超过255，则返回到0，之后继续自增；
DECR：同上面的DECR一样，也是把当前模板值自减1，但如果值低于0，则为255，之后继续自减。
4. D3D11中针对模板缓冲区的操作
之前我们使用过混合，在使用混合，我们首先要创建一个BlendState，然后通过SetBlendState来使用它。同样，这里我们要使用模板缓冲区，也是首先创建相应的DepthStencilState，然后SetDepthStencilState。在D3D11中对应的函数为：
HRESULT CreateDepthStencilState( [in] const D3D11_DEPTH_STENCIL_DESC *pDepthStencilDesc, [out] ID3D11DepthStenc
http://www.codeforces.com/problemset/problem/70/D
两种操作
1：增加一个点，会形成一个新的凸包
2：判断某个点是否在凸包内
有两种方法可以做，不过都类似的，都是根据求凸包的方法来做的。
比如，用水平序求凸包的时候，会有两条凸线，一条上凸折线，一条下凸折线，那么判断一个点在这个凸包内就是判断这个点是否在上凸折线的下方以及是否在下凸折线的上方
加入一个点的时候，我们需要找到凸线上水平序相邻的两个点，然后向两边不停的删点，直到满足凸包的定义为止
找到相邻的两个点可以用平衡树，用stl的话会简便很多很多。
注：一个小细节，传参数的时候没加引用，直接TLE了
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 100010;
#define foreach(i,n) for(__typeof(n.begin()) i = n.begin(); i!=n.end(); i++)
typedef pair<int, int> pii;
typedef long long lld;
#define MP make_pair
#define X first
#define Y second
map<int, int> Convex[2];
map<int, int>::iterator it, p, q;
lld cross(pii a, pii b, pii c) {
return (lld) (b.X - a.X) *(c.Y - a.Y) - (lld) (b.Y - a.Y) *(c.X - a.X);
}
bool judge(map<int, int> &st, int x, int y) {
if (!st.size())
return false;
if (st.find(x) != st.end())
return y >= st[x];
if (x < st.begin()->X || (--st.end())->X < x)
return false;
it = st.lower_bound(x);
p = q = it;
p--;
return cross(MP(x, y), *q, *p) <= 0;
}
void insert(map<int, int> &st, int x, int y) {
if (judge(st, x, y))
return;
st[x] = y;
it = st.find(x);
for (; it != st.begin();) {
p = it;
p--;
if (p == st.begin())
break;
q = p;
q--;
if (cross(*it, *p, *q) >= 0)
st.erase(p);
else
break;
}
it = st.find(x);
while(true) {
p = it;
p++;
if (p == st.end())
break;
q = p;
q++;
if(q==st.end()) break;
if (cross(*it, *p, *q) <= 0)
st.erase(p);
else
break;
}
}
int main() {
int Q, op, x, y;
scanf("%d", &Q);
while (Q--) {
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
insert(Convex[0], x, y);
insert(Convex[1], x, -y);
} else {
bool ans1 = judge(Convex[0], x, y) ;
bool ans2 = judge(Convex[1], x, -y);
if (ans1 && ans2)
puts("YES");
else
puts("NO");
}
}
return 0;
}二、一致性
1、一致性示例，如下程序：
#include "stdafx.h"
#include "iostream"
class string
{
public:
string()
{
str_ = new char[80];
len_ = 80;
}
string(int len)
{
str_ = new char[len];
len_ = len;
}
string(char *p)
{
len_ = strlen(p);
str_ = new char[len_];
strcpy(str_, p);
}
string(string &str);
~string()
{
delete[] str_;
}
public:
void Assign(char *str)
{
strcpy(str_, str);
len_ = strlen(str);
}
void Print()
{
std::cout << str_ << std::endl;
}
void concat(string &a, string &b);
private:
char *str_;
int len_;
};
string::string(string &str)
{
len_ = str.len_;
str_ = new char[len_];
strcpy(str_, str.str_);
}
void string::concat(string &a, string &b)
{
len_ = a.len_ + b.len_;
str_ = new char[len_];
strcpy(str_, a.str_);
strcat(str_, b.str_);
}
int _tmain(int argc, _TCHAR* argv[])
{
char *str = "The wheel that squeaks the loudest\n";
string a(str);
string b;
string author("Josh Billings\n");
string both;
string quote;
b.Assign("Is the one that gets the grease\n");
both.concat(a, b);
quote.concat(both, author);
quote.Print();
return 0;
}不足的地方
a、应该明确定义的状态
比如使用了string x, y(128); x.print();
那现在x的值是不确定的，输出的时候必要要等到’\0’才会停止(所有有构造函数应该使得对象处于明确的定义状态)
b、物理状态的一致性
看两段代码
string(char *p)
{
len_ = strlen(p);
str_ = new char[len_ + 1];
strcpy(str_, p);
}void string::concat(string &a, string &b)
{
len_ = a.len_ + b.len_;
str_ = new char[len_];
strcpy(str_, a.str_);
strcat(str_, b.str_);
}在这两个函数中len_所表示的含义有两个，一个是字符串的长度，另外一个是数组的长度；显然，len_的这两种含义都是有意义的，但在所有的构造函数及其他的成员函数中，必须只能有一种(所有的成员必须只有一个明确的定义，用一致的方式来定义对象的状态，这需要识别出类不变性)
c、动态内存的一致性
看这里的三段代码：
string()
{
str_ = new char[80];
len_ = 80;
}string(int len)
{
str_ = new char[len];
len_ = len;
}void string::concat(string &a, string &b)
{
len_ = a.len_ + b.len_;
str_ = new char[len_];
strcpy(str_, a.str_);
strcat(str_, b.str_);
}可以看到，上面动态分配的内存都是不一致的；要做到一致，有两种选择，一是只能是确保一开始分配的空间足够大，二是对每个字符串值都动态地决定数组的大小以保证安全。
这两种方法都可以用在类中，但只能使用其中的一种，以保持类的一致性，而不应该将这两种方法混合使用。否则，在使用这个类时，不得不去了解在接口中不同操作之间的不用约定(类的接口定义应该是一致的--------避免产生困惑)
d、动态内存的回收
来看字符串连接的一个问题
void string::concat(string &a, string &b)
{
len_ = a.len_ + b.len_;
str_ = new char[len_];
strcpy(str_, a.str_);
strcat(str_, b.str_);
}原来的空间显然被泄露掉了(对于每个new操作，都要有相应的delete操作)
看看重新设计的一个string类
#include "stdafx.h"
#include "iostream"
class string
{
public:
string();
string(const char *pStr);
string(string& str);
~string();
const char *content() const;
string& operator=(const char *pStr);
string& operator=(const string &str);
private:
char *string_;
int length_;
};
char *Strdup(const char *pStr)
{
char *pTemp = new char[strlen(pStr) + 1];
strcpy(pTemp, pStr);
return pTemp;
}
string::string()
{
string_ = 0;
length_ = 0;
}
string::string(const char *pStr)
{
string_ = pStr ? Strdup(pStr) : 0;
length_ = pStr ? strlen(string_) : 0;
}
string::string(string& str)
{
if (str.string_)
{
string_ = Strdup(str.string_);
length_ = strlen(string_);
}
else
{
string_ = 0;
length_ = 0;
}
}
string::~string()
{
if (string_)
{
delete[] string_;
}
}
const char *string::content() const
{
return string_ ? string_ : 0;
}
string& string::operator=(const char *pStr)
{
delete[] string_;
string_ = pStr ? Strdup(pStr) : 0;
length_ = pStr ? strlen(string_) : 0;
return *this;
}
string& string::operator=(const string &str)
{
delete[] string_;
string_ = str.string_ ? Strdup(str.string_) : 0;
length_ = string_ ? strlen(string_) : 0;
return *this;
}
int _tmain(int argc, _TCHAR* argv[])
{
string author("zengraoli");
return 0;
}该类使用了动态分配的形式，这样更能有效的避免数组的溢出
但是这里还有一些不足的地方：
a、冗余
length_的引入，一开始是为了表示字符串的长度，但是在这里这个信息却从来没有使用过。在string中，当每次需要字符串长度时，这个值都将在辅助函数Strdup中重新计算，所以这个状态信息是多余的(避免对从不使用的状态信息进行计算和存储)
b、在operator=中存在的一些问题
可以看到在operator=(const string &str)上面，先是delete，虽然不太容易写出像x=x这样的表达式，但是在程序中可能会简接地导致这种复赋值运算的发生(如果a和b碰巧都是引用了同一个string对象，纳闷呢a=b就等价于x=x)。虽然先delete就会导致操作未定义的内存。
所以最好的方式是首先处理自赋值
string& string::operator=(const string &str)
{
if (&str == this)
{
return *this;
}
delete[] string_;
string_ = str.string_ ? Strdup(str.string_) : 0;
length_ = string_ ? strlen(string_) : 0;
return *this;
} 对于operator=(const char *pStr)中的delete操作，可能会导致问题的情况是