简单的测试题3

发表于 2017-09-23 更新于 2020-09-08 阅读次数：本文字数： 25k 阅读时长 ≈ 22 分钟

概述

简单的测试题3是完整的NOIp Senior，分2天，目前只有PDF版本的题目，所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。

另外，借助pdf2htmlEX，题目和题解转为HTML版本：

day1
- solution
day2
- solution

可以尝试在这里提交：fact core_region

被移除的题目

2.最近点对(pair.cpp/c/pas)

题目描述

二维平面上有N个点($2\le N\le200,000$)，编号$1\ldots N$。两点之间的距离为欧几里得距离，即$dist_{i,j}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。

现在请求出所有点对中，距离最小的点对间的距离的平方。

输入格式(pair.in)

第一行一个整数N

接下来N行，每行两个整数$x_i,y_i$($0\le x_i,y_i\le1,000,000,000$)

输出格式(pair.out)

一个整数表示最近点对间距离的平方

输入样例

输出样例

样例解释

最近的点对是(1,2)和(2,3)，距离的平方为$1^2+2^2=5$。

数据范围

本题打包测试，必须通过一个子任务中的所有测试点才能得到对应的分值。

subtask1(30%):$N\le5,000$
subtask2(30%):$N\le50,000$
subtask3(20%):$N\le200,000;;0\le x_i,y_i\le1,000$
subtask4(20%):$N\le200,000$

对于100%的数据，$N\le200,000;;0\le x_i,y_i\le1,000,000,000$。

标程

day1

fact.cpp

#include<fstream>
#include<string>
#include<sstream>
using namespace std;

__float128 lgammaq (__float128);
__float128 logq (__float128);
__float128 powq (__float128, __float128);
__float128 scalbnq (__float128, int);

#define M_LN10q		2.3025850929940456840179914546843642Q  /* log_e 10 */

/* Main union type we use to manipulate the floating-point type.  */
typedef union
{
  __float128 value;

  struct
  {
    unsigned long long mant_low:64;
    unsigned long long mant_high:48;
    unsigned exponent:15;
    unsigned negative:1;
  } ieee;

  struct
  {
    unsigned long long low;
    unsigned long long high;
  } words64;

  struct
  {
    unsigned w3;
    unsigned w2;
    unsigned w1;
    unsigned w0;
  } words32;

  struct
  {
    unsigned long long mant_low:64;
    unsigned long long mant_high:47;
    unsigned quiet_nan:1;
    unsigned exponent:15;
    unsigned negative:1;
  } nan;

} ieee854_float128;


/* Get two 64 bit ints from a long double.  */
#define GET_FLT128_WORDS64(ix0,ix1,d)  \
do {                                   \
  ieee854_float128 u;                  \
  u.value = (d);                       \
  (ix0) = u.words64.high;              \
  (ix1) = u.words64.low;               \
} while (0)

/* Get the more significant 64 bits of a long double mantissa.  */
#define GET_FLT128_MSW64(v,d)          \
do {                                   \
  ieee854_float128 u;                  \
  u.value = (d);                       \
  (v) = u.words64.high;                \
} while (0)

/* Set the more significant 64 bits of a long double mantissa from an int.  */
#define SET_FLT128_MSW64(d,v)          \
do {                                   \
  ieee854_float128 u;                  \
  u.value = (d);                       \
  u.words64.high = (v);                \
  (d) = u.value;                       \
} while (0)

static const __float128 one = 1.0Q;
static const __float128 huge = 1.0e4000Q;

/* log gamma(x) = ( x - 0.5 ) * log(x) - x + LS2PI + 1/x P(1/x^2)
   1/x <= 0.0741 (x >= 13.495...)
   Peak relative error 1.5e-36  */
static const __float128 ls2pi = 9.1893853320467274178032973640561763986140E-1Q;
#define NRASY 12
static const __float128 RASY[NRASY + 1] =
{
  8.333333333333333333333333333310437112111E-2Q,
 -2.777777777777777777777774789556228296902E-3Q,
  7.936507936507936507795933938448586499183E-4Q,
 -5.952380952380952041799269756378148574045E-4Q,
  8.417508417507928904209891117498524452523E-4Q,
 -1.917526917481263997778542329739806086290E-3Q,
  6.410256381217852504446848671499409919280E-3Q,
 -2.955064066900961649768101034477363301626E-2Q,
  1.796402955865634243663453415388336954675E-1Q,
 -1.391522089007758553455753477688592767741E0Q,
  1.326130089598399157988112385013829305510E1Q,
 -1.420412699593782497803472576479997819149E2Q,
  1.218058922427762808938869872528846787020E3Q
};


/* Evaluate P[n] x^n  +  P[n-1] x^(n-1)  +  ...  +  P[0] */

static __float128
neval (__float128 x, const __float128 *p, int n)
{
  __float128 y;

  p += n;
  y = *p--;
  do
    {
      y = y * x + *p--;
    }
  while (--n > 0);
  return y;
}


__float128
lgammaq (__float128 x)
{
  __float128 p, q;

  q = ls2pi - x;
  q = (x - 0.5Q) * logq (x) + q;
  if (x > 1.0e18Q)
    return (q);

  p = 1.0Q / (x * x);
  q += neval (p, RASY, NRASY) / x;
  return (q);
}

/* log(1+x) = x - .5 x^2 + x^3 l(x)
   -.0078125 <= x <= +.0078125
   peak relative error 1.2e-37 */
static const __float128
l3 =   3.333333333333333333333333333333336096926E-1Q,
l4 =  -2.499999999999999999999999999486853077002E-1Q,
l5 =   1.999999999999999999999999998515277861905E-1Q,
l6 =  -1.666666666666666666666798448356171665678E-1Q,
l7 =   1.428571428571428571428808945895490721564E-1Q,
l8 =  -1.249999999999999987884655626377588149000E-1Q,
l9 =   1.111111111111111093947834982832456459186E-1Q,
l10 = -1.000000000000532974938900317952530453248E-1Q,
l11 =  9.090909090915566247008015301349979892689E-2Q,
l12 = -8.333333211818065121250921925397567745734E-2Q,
l13 =  7.692307559897661630807048686258659316091E-2Q,
l14 = -7.144242754190814657241902218399056829264E-2Q,
l15 =  6.668057591071739754844678883223432347481E-2Q;

/* Lookup table of ln(t) - (t-1)
    t = 0.5 + (k+26)/128)
    k = 0, ..., 91   */
static const __float128 logtbl[92] = {
-5.5345593589352099112142921677820359632418E-2Q,
-5.2108257402767124761784665198737642086148E-2Q,
-4.8991686870576856279407775480686721935120E-2Q,
-4.5993270766361228596215288742353061431071E-2Q,
-4.3110481649613269682442058976885699556950E-2Q,
-4.0340872319076331310838085093194799765520E-2Q,
-3.7682072451780927439219005993827431503510E-2Q,
-3.5131785416234343803903228503274262719586E-2Q,
-3.2687785249045246292687241862699949178831E-2Q,
-3.0347913785027239068190798397055267411813E-2Q,
-2.8110077931525797884641940838507561326298E-2Q,
-2.5972247078357715036426583294246819637618E-2Q,
-2.3932450635346084858612873953407168217307E-2Q,
-2.1988775689981395152022535153795155900240E-2Q,
-2.0139364778244501615441044267387667496733E-2Q,
-1.8382413762093794819267536615342902718324E-2Q,
-1.6716169807550022358923589720001638093023E-2Q,
-1.5138929457710992616226033183958974965355E-2Q,
-1.3649036795397472900424896523305726435029E-2Q,
-1.2244881690473465543308397998034325468152E-2Q,
-1.0924898127200937840689817557742469105693E-2Q,
-9.6875626072830301572839422532631079809328E-3Q,
-8.5313926245226231463436209313499745894157E-3Q,
-7.4549452072765973384933565912143044991706E-3Q,
-6.4568155251217050991200599386801665681310E-3Q,
-5.5356355563671005131126851708522185605193E-3Q,
-4.6900728132525199028885749289712348829878E-3Q,
-3.9188291218610470766469347968659624282519E-3Q,
-3.2206394539524058873423550293617843896540E-3Q,
-2.5942708080877805657374888909297113032132E-3Q,
-2.0385211375711716729239156839929281289086E-3Q,
-1.5522183228760777967376942769773768850872E-3Q,
-1.1342191863606077520036253234446621373191E-3Q,
-7.8340854719967065861624024730268350459991E-4Q,
-4.9869831458030115699628274852562992756174E-4Q,
-2.7902661731604211834685052867305795169688E-4Q,
-1.2335696813916860754951146082826952093496E-4Q,
-3.0677461025892873184042490943581654591817E-5Q,
 0.0000000000000000000000000000000000000000E0Q,
-3.0359557945051052537099938863236321874198E-5Q,
-1.2081346403474584914595395755316412213151E-4Q,
-2.7044071846562177120083903771008342059094E-4Q,
-4.7834133324631162897179240322783590830326E-4Q,
-7.4363569786340080624467487620270965403695E-4Q,
-1.0654639687057968333207323853366578860679E-3Q,
-1.4429854811877171341298062134712230604279E-3Q,
-1.8753781835651574193938679595797367137975E-3Q,
-2.3618380914922506054347222273705859653658E-3Q,
-2.9015787624124743013946600163375853631299E-3Q,
-3.4938307889254087318399313316921940859043E-3Q,
-4.1378413103128673800485306215154712148146E-3Q,
-4.8328735414488877044289435125365629849599E-3Q,
-5.5782063183564351739381962360253116934243E-3Q,
-6.3731336597098858051938306767880719015261E-3Q,
-7.2169643436165454612058905294782949315193E-3Q,
-8.1090214990427641365934846191367315083867E-3Q,
-9.0486422112807274112838713105168375482480E-3Q,
-1.0035177140880864314674126398350812606841E-2Q,
-1.1067990155502102718064936259435676477423E-2Q,
-1.2146457974158024928196575103115488672416E-2Q,
-1.3269969823361415906628825374158424754308E-2Q,
-1.4437927104692837124388550722759686270765E-2Q,
-1.5649743073340777659901053944852735064621E-2Q,
-1.6904842527181702880599758489058031645317E-2Q,
-1.8202661505988007336096407340750378994209E-2Q,
-1.9542647000370545390701192438691126552961E-2Q,
-2.0924256670080119637427928803038530924742E-2Q,
-2.2346958571309108496179613803760727786257E-2Q,
-2.3810230892650362330447187267648486279460E-2Q,
-2.5313561699385640380910474255652501521033E-2Q,
-2.6856448685790244233704909690165496625399E-2Q,
-2.8438398935154170008519274953860128449036E-2Q,
-3.0058928687233090922411781058956589863039E-2Q,
-3.1717563112854831855692484086486099896614E-2Q,
-3.3413836095418743219397234253475252001090E-2Q,
-3.5147290019036555862676702093393332533702E-2Q,
-3.6917475563073933027920505457688955423688E-2Q,
-3.8723951502862058660874073462456610731178E-2Q,
-4.0566284516358241168330505467000838017425E-2Q,
-4.2444048996543693813649967076598766917965E-2Q,
-4.4356826869355401653098777649745233339196E-2Q,
-4.6304207416957323121106944474331029996141E-2Q,
-4.8285787106164123613318093945035804818364E-2Q,
-5.0301169421838218987124461766244507342648E-2Q,
-5.2349964705088137924875459464622098310997E-2Q,
-5.4431789996103111613753440311680967840214E-2Q,
-5.6546268881465384189752786409400404404794E-2Q,
-5.8693031345788023909329239565012647817664E-2Q,
-6.0871713627532018185577188079210189048340E-2Q,
-6.3081958078862169742820420185833800925568E-2Q,
-6.5323413029406789694910800219643791556918E-2Q,
-6.7595732653791419081537811574227049288168E-2Q
};

/* ln(2) = ln2a + ln2b with extended precision. */
static const __float128
  ln2a = 6.93145751953125e-1Q,
  ln2b = 1.4286068203094172321214581765680755001344E-6Q;

__float128
logq (__float128 x)
{
  __float128 z, y, w;
  ieee854_float128 u, t;
  unsigned int m;
  int k, e;

  u.value = x;
  m = u.words32.w0;

  /* Extract exponent and reduce domain to 0.703125 <= u < 1.40625  */
  e = (int) (m >> 16) - (int) 0x3ffe;
  m &= 0xffff;
  u.words32.w0 = m | 0x3ffe0000;
  m |= 0x10000;
  /* Find lookup table index k from high order bits of the significand. */
  if (m < 0x16800)
    {
      k = (m - 0xff00) >> 9;
      /* t is the argument 0.5 + (k+26)/128
	 of the nearest item to u in the lookup table.  */
      t.words32.w0 = 0x3fff0000 + (k << 9);
      t.words32.w1 = 0;
      t.words32.w2 = 0;
      t.words32.w3 = 0;
      u.words32.w0 += 0x10000;
      e -= 1;
      k += 64;
    }
  else
    {
      k = (m - 0xfe00) >> 10;
      t.words32.w0 = 0x3ffe0000 + (k << 10);
      t.words32.w1 = 0;
      t.words32.w2 = 0;
      t.words32.w3 = 0;
    }
  /* On this interval the table is not used due to cancellation error.  */
  if ((x <= 1.0078125Q) && (x >= 0.9921875Q))
    {
      z = x - 1.0Q;
      k = 64;
      t.value  = 1.0Q;
      e = 0;
    }
  else
    {
      /* log(u) = log( t u/t ) = log(t) + log(u/t)
	 log(t) is tabulated in the lookup table.
	 Express log(u/t) = log(1+z),  where z = u/t - 1 = (u-t)/t.
         cf. Cody & Waite. */
      z = (u.value - t.value) / t.value;
    }
  /* Series expansion of log(1+z).  */
  w = z * z;
  y = ((((((((((((l15 * z
		  + l14) * z
		 + l13) * z
		+ l12) * z
	       + l11) * z
	      + l10) * z
	     + l9) * z
	    + l8) * z
	   + l7) * z
	  + l6) * z
	 + l5) * z
	+ l4) * z
       + l3) * z * w;
  y -= 0.5 * w;
  y += e * ln2b;  /* Base 2 exponent offset times ln(2).  */
  y += z;
  y += logtbl[k-26]; /* log(t) - (t-1) */
  y += (t.value - 1.0Q);
  y += e * ln2a;
  return y;
}

static const __float128 bp[] = {
  1.0Q,
  1.5Q,
};

/* log_2(1.5) */
static const __float128 dp_h[] = {
  0.0,
  5.8496250072115607565592654282227158546448E-1Q
};

/* Low part of log_2(1.5) */
static const __float128 dp_l[] = {
  0.0,
  1.0579781240112554492329533686862998106046E-16Q
};

static const __float128
  two = 2.0Q,
  two113 = 1.0384593717069655257060992658440192E34Q,
  tiny = 1.0e-3000Q;

/* 3/2 log x = 3 z + z^3 + z^3 (z^2 R(z^2))
   z = (x-1)/(x+1)
   1 <= x <= 1.25
   Peak relative error 2.3e-37 */
static const __float128 LN[] =
{
 -3.0779177200290054398792536829702930623200E1Q,
  6.5135778082209159921251824580292116201640E1Q,
 -4.6312921812152436921591152809994014413540E1Q,
  1.2510208195629420304615674658258363295208E1Q,
 -9.9266909031921425609179910128531667336670E-1Q
};
static const __float128 LD[] =
{
 -5.129862866715009066465422805058933131960E1Q,
  1.452015077564081884387441590064272782044E2Q,
 -1.524043275549860505277434040464085593165E2Q,
  7.236063513651544224319663428634139768808E1Q,
 -1.494198912340228235853027849917095580053E1Q
  /* 1.0E0 */
};

/* exp(x) = 1 + x - x / (1 - 2 / (x - x^2 R(x^2)))
   0 <= x <= 0.5
   Peak relative error 5.7e-38  */
static const __float128 PN[] =
{
  5.081801691915377692446852383385968225675E8Q,
  9.360895299872484512023336636427675327355E6Q,
  4.213701282274196030811629773097579432957E4Q,
  5.201006511142748908655720086041570288182E1Q,
  9.088368420359444263703202925095675982530E-3Q,
};
static const __float128 PD[] =
{
  3.049081015149226615468111430031590411682E9Q,
  1.069833887183886839966085436512368982758E8Q,
  8.259257717868875207333991924545445705394E5Q,
  1.872583833284143212651746812884298360922E3Q,
  /* 1.0E0 */
};

static const __float128
  /* ln 2 */
  lg2 = 6.9314718055994530941723212145817656807550E-1Q,
  lg2_h = 6.9314718055994528622676398299518041312695E-1Q,
  lg2_l = 2.3190468138462996154948554638754786504121E-17Q,
  ovt = 8.0085662595372944372e-0017Q,
  /* 2/(3*log(2)) */
  cp = 9.6179669392597560490661645400126142495110E-1Q,
  cp_h = 9.6179669392597555432899980587535537779331E-1Q,
  cp_l = 5.0577616648125906047157785230014751039424E-17Q;

__float128
powq (__float128 x, __float128 y)
{
  __float128 z, ax, z_h, z_l, p_h, p_l;
  __float128 y1, t1, t2, r, s, t, u, v, w;
  __float128 s2, s_h, s_l, t_h, t_l;
  int i, j, k, n;
  unsigned ix;
  int hx;
  ieee854_float128 o, p;

  p.value = x;
  hx = p.words32.w0;
  ix = hx & 0x7fffffff;

  ax = x;

  n = 0;
  /* take care subnormal number */
  if (ix < 0x00010000)
    {
      ax *= two113;
      n -= 113;
      o.value = ax;
      ix = o.words32.w0;
    }
  n += ((ix) >> 16) - 0x3fff;
  j = ix & 0x0000ffff;
  /* determine interval */
  ix = j | 0x3fff0000;		/* normalize ix */
  if (j <= 0x3988)
    k = 0;			/* |x|<sqrt(3/2) */
  else if (j < 0xbb67)
    k = 1;			/* |x|<sqrt(3)   */
  else
    {
      k = 0;
      n += 1;
      ix -= 0x00010000;
    }

  o.value = ax;
  o.words32.w0 = ix;
  ax = o.value;

  /* compute s = s_h+s_l = (x-1)/(x+1) or (x-1.5)/(x+1.5) */
  u = ax - bp[k];		/* bp[0]=1.0, bp[1]=1.5 */
  v = one / (ax + bp[k]);
  s = u * v;
  s_h = s;

  o.value = s_h;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  s_h = o.value;
  /* t_h=ax+bp[k] High */
  t_h = ax + bp[k];
  o.value = t_h;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  t_h = o.value;
  t_l = ax - (t_h - bp[k]);
  s_l = v * ((u - s_h * t_h) - s_h * t_l);
  /* compute log(ax) */
  s2 = s * s;
  u = LN[0] + s2 * (LN[1] + s2 * (LN[2] + s2 * (LN[3] + s2 * LN[4])));
  v = LD[0] + s2 * (LD[1] + s2 * (LD[2] + s2 * (LD[3] + s2 * (LD[4] + s2))));
  r = s2 * s2 * u / v;
  r += s_l * (s_h + s);
  s2 = s_h * s_h;
  t_h = 3.0 + s2 + r;
  o.value = t_h;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  t_h = o.value;
  t_l = r - ((t_h - 3.0) - s2);
  /* u+v = s*(1+...) */
  u = s_h * t_h;
  v = s_l * t_h + t_l * s;
  /* 2/(3log2)*(s+...) */
  p_h = u + v;
  o.value = p_h;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  p_h = o.value;
  p_l = v - (p_h - u);
  z_h = cp_h * p_h;		/* cp_h+cp_l = 2/(3*log2) */
  z_l = cp_l * p_h + p_l * cp + dp_l[k];
  /* log2(ax) = (s+..)*2/(3*log2) = n + dp_h + z_h + z_l */
  t = (__float128) n;
  t1 = (((z_h + z_l) + dp_h[k]) + t);
  o.value = t1;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  t1 = o.value;
  t2 = z_l - (((t1 - t) - dp_h[k]) - z_h);
  s = one;
  
  /* split up y into y1+y2 and compute (y1+y2)*(t1+t2) */
  y1 = y;
  o.value = y1;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  y1 = o.value;
  p_l = (y - y1) * t1 + y * t2;
  p_h = y1 * t1;
  z = p_l + p_h;
  o.value = z;
  j = o.words32.w0;
  /* compute 2**(p_h+p_l) */
  i = j & 0x7fffffff;
  k = (i >> 16) - 0x3fff;
  n = 0;
  if (i > 0x3ffe0000)
    {				/* if |z| > 0.5, set n = [z+0.5] */
      n = z + 0.5Q;
      t = n;
      p_h -= t;
    }
  t = p_l + p_h;
  o.value = t;
  o.words32.w3 = 0;
  o.words32.w2 &= 0xf8000000;
  t = o.value;
  u = t * lg2_h;
  v = (p_l - (t - p_h)) * lg2 + t * lg2_l;
  z = u + v;
  w = v - (z - u);
  /*  exp(z) */
  t = z * z;
  u = PN[0] + t * (PN[1] + t * (PN[2] + t * (PN[3] + t * PN[4])));
  v = PD[0] + t * (PD[1] + t * (PD[2] + t * (PD[3] + t)));
  t1 = z - t * u / v;
  r = (z * t1) / (t1 - two) - (w + z * w);
  z = one - (r - z);
  o.value = z;
  j = o.words32.w0;
  j += (n << 16);
  if ((j >> 16) <= 0)
    z = scalbnq (z, n);	/* subnormal output */
  else
    {
      o.words32.w0 = j;
      z = o.value;
    }
  return s * z;
}

static const __float128
two114 = 2.0769187434139310514121985316880384E+34Q, /* 0x4071000000000000, 0 */
twom114 = 4.8148248609680896326399448564623183E-35Q;/* 0x3F8D000000000000, 0 */

__float128
scalbnq (__float128 x, int n)
{
	long long k,hx,lx;
	GET_FLT128_WORDS64(hx,lx,x);
        k = (hx>>48)&0x7fff;		/* extract exponent */
        if (k==0) {				/* 0 or subnormal x */
            if ((lx|(hx&0x7fffffffffffffffULL))==0) return x; /* +-0 */
	    x *= two114;
	    GET_FLT128_MSW64(hx,x);
	    k = ((hx>>48)&0x7fff) - 114;
	}
        if (k==0x7fff) return x+x;		/* NaN or Inf */
	/* Now k and n are bounded we know that k = k+n does not
	   overflow.  */
        k = k+n;
        if (k > 0) 				/* normal result */
	    {SET_FLT128_MSW64(x,(hx&0x8000ffffffffffffULL)|(k<<48)); return x;}
        if (k <= -114)
        k += 114;				/* subnormal result */
	SET_FLT128_MSW64(x,(hx&0x8000ffffffffffffULL)|(k<<48));
        return x*twom114;
}

const int tbl_cnt=3;
const double tbl[tbl_cnt]={1.0,1.0,2.0};

ifstream fin("fact.in");
ofstream fout("fact.out");

int main()
{
	long long n;
	int k;
	fin>>n>>k;
	if(n<tbl_cnt)
	{
		fout.precision(k);
		fout<<tbl[n]<<"e+0\n";
		return 0;
	}
	__float128 ans=lgammaq(n+1.0Q)/M_LN10q;
	unsigned long long len=ans;
	ans=powq(10.0Q,ans-len+k-1);
	long long frac=ans;
	ans-=frac;
	if(ans>=0.5Q)
		frac++;
	stringstream ss;
	ss<<frac;
	string s=ss.str();
	while(s[s.length()-1]=='0')
		s.erase(s.length()-1);
	if(s.length()>1)
		s.insert(1,1,'.');
	fout<<s<<"e+"<<len<<endl;
	return 0;
}

lasers.cpp

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("lasers.in");
ofstream fout("lasers.out");
const int N = 300005, INF = 0x3f3f3f3f;
int x[N], y[N], d[N * 2];
pair<int, int> e[N];
vector<int> mat[N * 2];
int main()
{
	int n, sx, sy, tx, ty;
	fin >> n >> sx >> sy >> tx >> ty;
	for (int i = 1; i <= n; i++)
	{
		fin >> e[i].first >> e[i].second;
		x[i] = e[i].first;
		y[i] = e[i].second;
	}
	x[n + 1] = sx;
	x[n + 2] = tx;
	y[n + 1] = sy;
	y[n + 2] = ty;
	sort(x + 1, x + n + 3);
	sort(y + 1, y + n + 3);
	sx = lower_bound(x + 1, x + n + 3, sx) - x;
	sy = lower_bound(y + 1, y + n + 3, sy) - y + n + 2;
	tx = lower_bound(x + 1, x + n + 3, tx) - x;
	ty = lower_bound(y + 1, y + n + 3, ty) - y + n + 2;
	for (int i = 1; i <= n; i++)
	{
		e[i].first = lower_bound(x + 1, x + n + 3, e[i].first) - x;
		e[i].second = lower_bound(y + 1, y + n + 3, e[i].second) - y + n + 2;
		mat[e[i].first].push_back(e[i].second);
		mat[e[i].second].push_back(e[i].first);
	}
	fill(d + 1, d + n + 2 + n + 2 + 1, INF);
	d[sx] = d[sy] = 0;
	queue<int> Q;
	Q.push(sx);
	Q.push(sy);
	while (!Q.empty())
	{
		int k = Q.front();
		Q.pop();
		for (auto v : mat[k])
			if (d[v] == INF)
			{
				d[v] = d[k] + 1;
				Q.push(v);
			}
	}
	fout << min(d[tx], d[ty]) << endl;
	return 0;
}

bales.cpp

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("bales.in");
ofstream fout("bales.out");
const int N = 1000005, M = 300005;
struct quest
{
	int l, r, min, id;
	bool operator<(const quest &rhs) const
	{
		return min > rhs.min;
	}
} a[M], b[M];
int n, m, f[N];
int getf(int x)
{
	return f[x] == x ? x : f[x] = getf(f[x]);
}
bool check(int mid)
{
	int cc = 0;
	for (int i = 1; i <= m; i++)
		if (a[i].id <= mid)
			b[++cc] = a[i];
	for (int i = 0; i <= n; i++)
		f[i] = i;
	for (int i = 1, j; i <= cc; i = j)
	{
		int minx = b[i].l, maxx = b[i].l, miny = b[i].r, maxy = b[i].r;
		for (j = i + 1; j <= cc && b[j].min == b[i].min; j++)
		{
			minx = min(minx, b[j].l);
			maxx = max(maxx, b[j].l);
			miny = min(miny, b[j].r);
			maxy = max(maxy, b[j].r);
		}
		if (maxx > getf(miny))
			return false;
		while (minx <= maxy)
			if (getf(maxy) == maxy)
				f[maxy--] = getf(minx - 1);
			else
				maxy = getf(maxy);
	}
	return true;
}
int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> a[i].l >> a[i].r >> a[i].min;
		a[i].id = i;
	}
	sort(a + 1, a + m + 1);
	int l = 1, r = m, ans = 1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			l = mid + 1;
			ans = mid;
		}
		else
			r = mid - 1;
	}
	fout << (ans + 1) % (m + 1) << endl;
	return 0;
}

day2

corral.cpp

#include <fstream>
#include <algorithm>
#include <utility>
#include <limits>
using namespace std;
ifstream fin("corral.in");
ofstream fout("corral.out");
const int N = 3005;
const long long INF = numeric_limits<long long>::max();
pair<long long, long long> p[N];
long long x[N], y[N];
short s[N][N];
int main()
{
	int c, n;
	fin >> c >> n;
	for (int i = 1; i <= n; i++)
	{
		fin >> p[i].first >> p[i].second;
		x[i] = p[i].first;
		y[i] = p[i].second;
	}
	sort(x + 1, x + n + 1);
	sort(y + 1, y + n + 1);
	int xn = unique(x + 1, x + n + 1) - x - 1, yn = unique(y + 1, y + n + 1) - y - 1;
	for (int i = 1; i <= n; i++)
	{
		p[i].first = lower_bound(x + 1, x + xn + 1, p[i].first) - x;
		p[i].second = lower_bound(y + 1, y + yn + 1, p[i].second) - y;
		s[p[i].first][p[i].second]++;
	}
	for (int i = 1; i <= xn; i++)
		for (int j = 1; j <= yn; j++)
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	long long ans = INF;
	x[xn + 1] = y[yn + 1] = INF;
	for (int x1 = 1; x1 <= xn; x1++)
	{
		long long now = 0;
		int x2 = x1 + 1, y1 = 1, y2 = 2, cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
		for (;;)
		{
			while (cnt < c && (x2 <= xn || y2 <= yn))
			{
				now = min(x[x2] - x[x1], y[y2] - y[y1]);
				for (; x[x2] - x[x1] <= now; x2++)
					;
				for (; y[y2] - y[y1] <= now; y2++)
					;
				cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
			}
			if (cnt < c)
				break;
			ans = min(ans, now + 1);
			if (++y1 > yn)
				break;
			if (y2 == y1)
			{
				y2 = y1 + 1;
				now = 0;
			}
			else
				now -= y[y1] - y[y1 - 1];
			for (; x[x2 - 1] - x[x1] > now; x2--)
				;
			cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
		}
	}
	fout << ans << endl;
	return 0;
}

qkiller.cpp

#include <fstream>
#include <ctime>
#include <algorithm>
using namespace std;
ifstream fin("qkiller.in");
ofstream fout("qkiller.out");
const int n = 100000, A = 48271, MOD = 2147483647;
int a[n + 5], id[n + 5], ans[n + 5];
int main()
{
	int type;
	fin >> type;
	long long seed;
	if (type == 4)
	{
		tm rec;
		char c;
		fin >> rec.tm_year >> c >> rec.tm_mon >> c >> rec.tm_mday >> rec.tm_hour >> c >> rec.tm_min >> c >> rec.tm_sec;
		rec.tm_year -= 1900;
		rec.tm_mon--;
		seed = mktime(&rec);
	}
	for (int i = 1; i <= n; i++)
	{
		fin >> a[i];
		id[i] = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
	{
		int pos;
		switch (type)
		{
		case 1:
			pos = (i + n) / 2;
			break;
		case 2:
			pos = i;
			break;
		case 3:
			pos = n;
			break;
		case 4:
			seed = seed * A % MOD;
			pos = seed % (n - i + 1) + i;
			break;
		}
		ans[id[pos]] = a[i];
		swap(id[i], id[pos]);
	}
	for (int i = 1; i <= n; i++)
		fout << ans[i] << endl;
	return 0;
}

landscape.cpp

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("landscape.in");
ofstream fout("landscape.out");
const int N = 100005;
int a[N], b[N];
int main()
{
	int n, x, y, z;
	fin >> n >> x >> y >> z;
	for (int i = 1; i <= n; i++)
		fin >> a[i] >> b[i];
	priority_queue<int, vector<int>, greater<int>> q1, q2;
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (; a[i] > b[i]; a[i]--)
		{
			int now = y;
			if (!q1.empty() && q1.top() + i * z < now)
			{
				now = q1.top() + i * z;
				q1.pop();
			}
			ans += now;
			q2.push(-now - i * z);
		}
		for (; a[i] < b[i]; a[i]++)
		{
			int now = x;
			if (!q2.empty() && q2.top() + i * z < now)
			{
				now = q2.top() + i * z;
				q2.pop();
			}
			ans += now;
			q1.push(-now - i * z);
		}
	}
	fout << ans << endl;
	return 0;
}

removed

pair.cpp

#include<fstream>
#include<algorithm>
#include<set>
using namespace std;
ifstream fin("pair.in");
ofstream fout("pair.out");
const int N=200005;
const long long INF=0x3f3f3f3f3f3f3f3fll;
pair<int,int> p[N];
int main()
{
	int n;
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>p[i].first>>p[i].second;
	sort(p+1,p+n+1);
	long long ans=INF;
	multiset<pair<int,int>> S;
	int j=1;
	for(int i=1;i<=n;i++)
	{
		for(;j<i&&(long long)(p[i].first-p[j].first)*(p[i].first-p[j].first)>=ans;j++)
			S.erase(S.find(make_pair(p[j].second,p[j].first)));
		auto ret=S.insert(make_pair(p[i].second,p[i].first));
		for(auto it=ret;it--!=S.begin();)
		{
			int dy=p[i].second-it->first;
			if((long long)dy*dy>=ans)
				break;
			int dx=p[i].first-it->second;
			ans=min(ans,(long long)dx*dx+(long long)dy*dy);
		}
		for(auto it=ret;++it!=S.end();)
		{
			int dy=it->first-p[i].second;
			if((long long)dy*dy>=ans)
				break;
			int dx=p[i].first-it->second;
			ans=min(ans,(long long)dx*dx+(long long)dy*dy);
		}
	}
	fout<<ans<<endl;
	return 0;
}