cf682E Alyona and Triangles

超、凢脫俗 2021-09-30 04:40 196阅读 0赞

You are given *n* points with integer coordinates on the plane. Points are given in a way such that there is no triangle, formed by any three of these *n* points, which area exceeds *S*.

Alyona tried to construct a triangle with integer coordinates, which contains all *n* points and which area doesn't exceed 4*S*, but, by obvious reason, had no success in that. Please help Alyona construct such triangle. Please note that vertices of resulting triangle are not necessarily chosen from *n* given points.

Input

In the first line of the input two integers *n* and *S* (3 ≤ *n* ≤ 5000, 1 ≤ *S* ≤ 1018) are given — the number of points given and the upper bound value of any triangle's area, formed by any three of given *n* points.

The next *n* lines describes given points: *i**th* of them consists of two integers *x**i* and *y**i*( - 108 ≤ *x**i*, *y**i* ≤ 108) — coordinates of *i**th* point.

It is guaranteed that there is at least one triple of points not lying on the same line.

Output

Print the coordinates of three points — vertices of a triangle which contains all *n* points and which area doesn't exceed 4*S*.

Coordinates of every triangle's vertex should be printed on a separate line, every coordinate pair should be separated by a single space. Coordinates should be an integers not exceeding 109 by absolute value.

It is guaranteed that there is at least one desired triangle. If there is more than one answer, print any of them.

Example

Input

4 1
    0 0
    1 0
    0 1
    1 1

Output

-1 0
    2 0
    0 2

Note

![1a2d1767c5316def0899d4097e6b2cf6_v_1499686779][]

要找个三角形把所有点都包在里面

画画图就会发现，只要在这些点中找个面积最大的三角形，然后对三条边都翻折过去变成一个4倍大的三角形就好了

面积最大的三角形找法有点迷……一开始就选123号点，然后每次尝试把一个点替换之后面积会不会变大

一直做到不再变大为止。

这玩意似乎有什么定理 可以证明2-stable point一定属于3-stable point?

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<cstdlib>
     5 #include<algorithm>
     6 #include<queue>
     7 #include<deque>
     8 #include<set>
     9 #include<map>
    10 #include<ctime>
    11 #define LL long long
    12 #define inf 0x7ffffff
    13 #define pa pair<int,int>
    14 #define pi 3.1415926535897932384626433832795028841971
    15 using namespace std;
    16 inline LL read()
    17 {
    18     LL x=0,f=1;char ch=getchar();
    19     while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
    20     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    21     return x*f;
    22 }
    23 inline void write(LL a)
    24 {
    25     if (a<0){printf("-");a=-a;}
    26     if (a>=10)write(a/10);
    27     putchar(a%10+'0');
    28 }
    29 inline void writeln(LL a){write(a);printf("\n");}
    30 LL n,k;
    31 struct point{
    32     LL x,y;
    33 }p[100010];
    34 int a,b,c;
    35 point operator +(point a,point b){
         return (point){a.x+b.x,a.y+b.y};}
    36 point operator -(point a,point b){
         return (point){a.x-b.x,a.y-b.y};}
    37 inline LL calc(int a,int b,int c)
    38 {
    39     LL x1=p[c].x-p[a].x,y1=p[c].y-p[a].y,x2=p[b].x-p[a].x,y2=p[b].y-p[a].y;
    40     LL ans=x1*y2-x2*y1;
    41     if (ans<0)ans=-ans;
    42     return ans;
    43 }
    44 int main()
    45 {
    46     n=read();k=read();
    47     for (int i=1;i<=n;i++)p[i].x=read(),p[i].y=read();
    48     a=1;b=2;c=3;
    49     bool refresh=0;
    50     while (!refresh)
    51     {
    52         refresh=1;
    53         for (int i=1;i<=n;i++)
    54         if (i!=a&&i!=b&&i!=c)
    55         {
    56             if (calc(a,b,c)<calc(i,b,c))a=i,refresh=0;
    57             else if (calc(a,b,c)<calc(a,i,c))b=i,refresh=0;
    58             else if (calc(a,b,c)<calc(a,b,i))c=i,refresh=0;
    59         }
    60     }
    61     point d=p[a]+p[b]-p[c],e=p[a]+p[c]-p[b],f=p[c]+p[b]-p[a];
    62     printf("%lld %lld\n",d.x,d.y);
    63     printf("%lld %lld\n",e.x,e.y);
    64     printf("%lld %lld\n",f.x,f.y);
    65 }

cf 682E

转载于:https://www.cnblogs.com/zhber/p/7153125.html

[1a2d1767c5316def0899d4097e6b2cf6_v_1499686779]: https://odzkskevi.qnssl.com/1a2d1767c5316def0899d4097e6b2cf6?v=1499686779
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/425fecf5eb124716a0bff2792e43817f.png